home *** CD-ROM | disk | FTP | other *** search
/ Hackers Matrix / Hacker's Matrix (nCite Software) (2003).iso / Tutorials / hTut_0047.txt < prev    next >
Text File  |  2002-12-13  |  124KB  |  2,545 lines

  1. Cryptography FAQ
  2.  
  3. Subject: Cryptography FAQ (01/10: Overview)
  4. Date: 18 Feb 1994 15:14:44 GMT
  5. Organization: The Crypt Cabal
  6.  
  7. Summary: Part 1 of 10 of the sci.crypt FAQ, Overview. Table of 
  8.  contents, contributors, feedback, archives, administrivia, changes.
  9.  
  10. Archive-name: cryptography-faq/part01
  11. Version: 1.0
  12. Last-modified: 93/08/23
  13.  
  14. This is the first of ten parts of the sci.crypt FAQ. The parts are
  15. mostly independent, but you should read this part before the rest. We
  16. don't have the time to send out missing parts by mail, so don't ask.
  17. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  18.  
  19. Disclaimer: This document is the product of the Crypt Cabal, a secret
  20. society which serves the National Secu---uh, no. Seriously, we're the
  21. good guys, and we've done what we can to ensure the completeness and
  22. accuracy of this document, but in a field of military and commercial
  23. importance like cryptography you have to expect that some people and
  24. organizations consider their interests more important than open
  25. scientific discussion. Trust only what you can verify firsthand.
  26. And don't sue us.
  27.  
  28. Many people have contributed to this FAQ. In alphabetical order:
  29. Eric Bach, Steve Bellovin, Dan Bernstein, Nelson Bolyard, Carl Ellison,
  30. Jim Gillogly, Mike Gleason, Doug Gwyn, Luke O'Connor, Tony Patti,
  31. William Setzer. We apologize for any omissions.
  32.  
  33. If you have suggestions, comments, or criticism, please let the current
  34. editors know by sending e-mail to crypt-comments@math.ncsu.edu. Bear in
  35. mind that this is a work in progress; there are some questions which we
  36. should add but haven't gotten around to yet. In making comments on
  37. additions it is most helpful if you are as specific as possible and 
  38. ideally even provide the actual exact text.
  39.  
  40. Archives: sci.crypt has been archived since October 1991 on
  41. ripem.msu.edu, though these archives are available only to U.S. and
  42. Canadian users. Another site is rpub.cl.msu.edu in /pub/crypt/sci.crypt/ 
  43. from Jan 1992. Please contact crypt-comments@math.ncsu.edu if you know of
  44. other archives.
  45.  
  46. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  47. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  48. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  49. sci.answers, and news.answers every 21 days.
  50.  
  51. Changes: a section at the end of this part 1 lists recent changes.  The
  52. fields `Last-Modified' and `Version' at the top of this part 1 track
  53. revisions.
  54.  
  55.  
  56. Table of Contents
  57. -----------------
  58.  
  59. 1. Overview
  60.  
  61. 2. Net Etiquette
  62. 2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
  63. 2.2. Do political discussions belong in sci.crypt?
  64. 2.3. How do I present a new encryption scheme in sci.crypt?
  65.  
  66. 3. Basic Cryptology
  67. 3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
  68. 3.2. What references can I start with to learn cryptology?
  69. 3.3. How does one go about cryptanalysis?
  70. 3.4. What is a brute-force search and what is its cryptographic relevance?
  71. 3.5. What are some properties satisfied by every strong cryptosystem?
  72. 3.6. If a cryptosystem is theoretically unbreakable, then is it
  73.   guaranteed analysis-proof in practice?
  74. 3.7. Why are many people still using cryptosystems that are
  75.   relatively easy to break?
  76. 3.8. What are the basic types of cryptanalytic `attacks'?
  77.  
  78. 4. Mathematical Cryptology
  79. 4.1. In mathematical terms, what is a private-key cryptosystem?
  80. 4.2. What is an attack?
  81. 4.3. What's the advantage of formulating all this mathematically?
  82. 4.4. Why is the one-time pad secure?
  83. 4.5. What's a ciphertext-only attack?
  84. 4.6. What's a known-plaintext attack?
  85. 4.7. What's a chosen-plaintext attack?
  86. 4.8. In mathematical terms, what can you say about brute-force attacks?
  87. 4.9. What's a key-guessing attack? What's entropy?
  88.  
  89. 5. Product Ciphers
  90. 5.1. What is a product cipher?
  91. 5.2. What makes a product cipher secure?
  92. 5.3. What are some group-theoretic properties of product ciphers?
  93. 5.4. What can be proven about the security of a product cipher?
  94. 5.5. How are block ciphers used to encrypt data longer than the block size?
  95. 5.6. Can symmetric block ciphers be used for message authentication?
  96. 5.7. What exactly is DES?
  97. 5.8. What is triple DES?
  98. 5.9. What is differential cryptanalysis?
  99. 5.10. How was NSA involved in the design of DES?
  100. 5.11. Is DES available in software?
  101. 5.12. Is DES available in hardware?
  102. 5.13. Can DES be used to protect classified information?
  103. 5.14. What are ECB, CBC, CFB, and OFB encryption?
  104.  
  105. 6. Public-Key Cryptography
  106. 6.1. What is public-key cryptography?
  107. 6.2. How does public-key cryptography solve cryptography's Catch-22?
  108. 6.3. What is the role of the `trapdoor function' in public key schemes?
  109. 6.4. What is the role of the `session key' in public key schemes?
  110. 6.5. What's RSA?
  111. 6.6. Is RSA secure?
  112. 6.7. What's the difference between the RSA and Diffie-Hellman schemes?
  113. 6.8. What is `authentication' and the `key distribution problem'?
  114. 6.9. How fast can people factor numbers?
  115. 6.10. What about other public-key cryptosystems?
  116. 6.11. What is the `RSA Factoring Challenge?'
  117.  
  118. 7. Digital Signatures
  119. 7.1. What is a one-way hash function?
  120. 7.2. What is the difference between public, private, secret, shared, etc.?
  121. 7.3. What are MD4 and MD5?
  122. 7.4. What is Snefru?
  123.  
  124. 8. Technical Miscellany
  125. 8.1. How do I recover from lost passwords in WordPerfect?
  126. 8.2. How do I break a Vigenere (repeated-key) cipher?
  127. 8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
  128. 8.4. Is the UNIX crypt command secure?
  129. 8.5. How do I use compression with encryption?
  130. 8.6. Is there an unbreakable cipher?
  131. 8.7. What does ``random'' mean in cryptography?
  132. 8.8. What is the unicity point (a.k.a. unicity distance)?
  133. 8.9. What is key management and why is it important?
  134. 8.10. Can I use pseudo-random or chaotic numbers as a key stream?
  135. 8.11. What is the correct frequency list for English letters?
  136. 8.12. What is the Enigma?
  137. 8.13. How do I shuffle cards?
  138. 8.14. Can I foil S/W pirates by encrypting my CD-ROM?
  139. 8.15. Can you do automatic cryptanalysis of simple ciphers?
  140. 8.16. What is the coding system used by VCR+?
  141.  
  142. 9. Other Miscellany
  143. 9.1. What is the National Security Agency (NSA)?
  144. 9.2. What are the US export regulations?
  145. 9.3. What is TEMPEST?
  146. 9.4. What are the Beale Ciphers, and are they a hoax?
  147. 9.5. What is the American Cryptogram Association, and how do I get in touch?
  148. 9.6. Is RSA patented?
  149. 9.7. What about the Voynich manuscript?
  150.  
  151. 10. References
  152. 10.1. Books on history and classical methods
  153. 10.2. Books on modern methods
  154. 10.3. Survey articles
  155. 10.4. Reference articles
  156. 10.5. Journals, conference proceedings
  157. 10.6. Other
  158. 10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
  159. 10.8. Electronic sources
  160. 10.9. RFCs (available from [FTPRF])
  161. 10.10. Related newsgroups
  162.  
  163. Changes
  164. -------
  165.  
  166. 930823 L.D.
  167.  
  168.   New sci.crypt archive site (1). NIST [FTPNS], cypherpunk FTP [FTPCP] sites 
  169.   added (10.6, 10.8), more info on security of RSA (6.3). Public key basics 
  170.   refined (6.1). RSA Factoring Challenge added (6.5). Added Changes section 
  171.   (1). Update of ACA address (9.5). C. Ellison modifications on compression 
  172.   (8.5) and attack types added (3.8). Info Security News in (10.5). New DES 
  173.   source [FTPAL].
  174.  
  175.  
  176.  
  177. Article 18264 of news.answers:
  178. Path: news.columbia.edu!sol.ctr.columbia.edu!destroyer!newsxfer.itd.umich.edu!gumby!wupost!usc!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
  179. From: crypt-comments@math.ncsu.edu
  180. Newsgroups: sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
  181. Subject: Cryptography FAQ (02/10: Net Etiquette)
  182. Supersedes: <cryptography-faq/part02_758782810@rtfm.mit.edu>
  183. Followup-To: poster
  184. Date: 18 Feb 1994 15:14:51 GMT
  185. Organization: The Crypt Cabal
  186. Lines: 91
  187. Approved: news-answers-request@MIT.Edu
  188. Expires: 25 Mar 1994 15:11:15 GMT
  189. Message-ID: <cryptography-faq/part02_761584275@rtfm.mit.edu>
  190. References: <cryptography-faq/part01_761584275@rtfm.mit.edu>
  191. Reply-To: crypt-comments@math.ncsu.edu
  192. NNTP-Posting-Host: bloom-picayune.mit.edu
  193. X-Last-Updated: 1993/10/10
  194. Originator: faqserv@bloom-picayune.MIT.EDU
  195. Xref: news.columbia.edu sci.crypt:21374 talk.politics.crypto:2942 sci.answers:899 news.answers:18264 talk.answers:149
  196.  
  197. Archive-name: cryptography-faq/part02
  198. Last-modified: 93/05/04
  199.  
  200.  
  201. This is the second of ten parts of the sci.crypt FAQ. The parts are
  202. mostly independent, but you should read the first part before the rest.
  203. We don't have the time to send out missing parts by mail, so don't ask.
  204. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  205.  
  206. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  207. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  208. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  209. sci.answers, and news.answers every 21 days.
  210.  
  211.  
  212.  
  213. Contents:
  214.  
  215. 2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
  216. 2.2. Do political discussions belong in sci.crypt?
  217. 2.3. How do I present a new encryption scheme in sci.crypt?
  218.  
  219.  
  220. 2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
  221.  
  222.   Read news.announce.newusers and news.answers for a few weeks. Always
  223.   make sure to read a newsgroup for some time before you post to it.
  224.   You'll be amazed how often the same question can be asked in the same
  225.   newsgroup. After a month you'll have a much better sense of what the
  226.   readers want to see.
  227.  
  228. 2.2. Do political discussions belong in sci.crypt?
  229.  
  230.   No. In fact some newsgroups (notably misc.legal.computing) were
  231.   created exactly so that political questions like ``Should RSA be
  232.   patented?'' don't get in the way of technical discussions. Many
  233.   sci.crypt readers also read misc.legal.computing, comp.org.eff.talk,
  234.   comp.patents, sci.math, comp.compression, et al.; for the benefit of
  235.   people who don't care about those other topics, try to put your
  236.   postings in the right group.
  237.  
  238.   Questions about microfilm and smuggling and other non-cryptographic
  239.   ``spy stuff'' don't belong in sci.crypt either.
  240.  
  241. 2.3. How do I present a new encryption scheme in sci.crypt?
  242.  
  243.   ``I just came up with this neat method of encryption. Here's some
  244.   ciphertext: FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it strong?'' Without a
  245.   doubt questions like this are the most annoying traffic on sci.crypt.
  246.  
  247.   If you have come up with an encryption scheme, providing some
  248.   ciphertext from it is not adequate. Nobody has ever been impressed by
  249.   random gibberish. Any new algorithm should be secure even if the
  250.   opponent knows the full algorithm (including how any message key is
  251.   distributed) and only the private key is kept secret. There are some
  252.   systematic and unsystematic ways to take reasonably long ciphertexts
  253.   and decrypt them even without prior knowledge of the algorithm, but
  254.   this is a time-consuming and possibly fruitless exercise which most
  255.   sci.crypt readers won't bother with.
  256.  
  257.   So what do you do if you have a new encryption scheme? First of all,
  258.   find out if it's really new. Look through this FAQ for references and
  259.   related methods. Familiarize yourself with the literature and the
  260.   introductory textbooks.
  261.  
  262.   When you can appreciate how your cryptosystem fits into the world at
  263.   large, try to break it yourself! You shouldn't waste the time of tens
  264.   of thousands of readers asking a question which you could have easily
  265.   answered on your own.
  266.  
  267.   If you really think your system is secure, and you want to get some
  268.   reassurance from experts, you might try posting full details of your
  269.   system, including working code and a solid theoretical explanation, to
  270.   sci.crypt. (Keep in mind that the export of cryptography is regulated
  271.   in some areas.)
  272.  
  273.   If you're lucky an expert might take some interest in what you posted.
  274.   You can encourage this by offering cash rewards---for instance, noted
  275.   cryptographer Ralph Merkle is offering $1000 to anyone who can break
  276.   Snefru-4---but there are no guarantees. If you don't have enough
  277.   experience, then most likely any experts who look at your system will
  278.   be able to find a flaw. If this happens, it's your responsibility to
  279.   consider the flaw and learn from it, rather than just add one more
  280.   layer of complication and come back for another round.
  281.  
  282.   A different way to get your cryptosystem reviewed is to have the NSA
  283.   look at it. A full discussion of this procedure is outside the scope
  284.   of this FAQ.
  285.  
  286.   Among professionals, a common rule of thumb is that if you want to
  287.   design a cryptosystem, you have to have experience as a cryptanalyst.
  288.  
  289.  
  290. Article 18266 of news.answers:
  291. Path: news.columbia.edu!sol.ctr.columbia.edu!destroyer!newsxfer.itd.umich.edu!gumby!wupost!usc!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv
  292. From: crypt-comments@math.ncsu.edu
  293. Newsgroups: sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
  294. Subject: Cryptography FAQ (03/10: Basic Cryptology)
  295. Supersedes: <cryptography-faq/part03_758782810@rtfm.mit.edu>
  296. Followup-To: poster
  297. Date: 18 Feb 1994 15:14:59 GMT
  298. Organization: The Crypt Cabal
  299. Lines: 251
  300. Approved: news-answers-request@MIT.Edu
  301. Expires: 25 Mar 1994 15:11:15 GMT
  302. Message-ID: <cryptography-faq/part03_761584275@rtfm.mit.edu>
  303. References: <cryptography-faq/part01_761584275@rtfm.mit.edu>
  304. Reply-To: crypt-comments@math.ncsu.edu
  305. NNTP-Posting-Host: bloom-picayune.mit.edu
  306. X-Last-Updated: 1993/10/10
  307. Originator: faqserv@bloom-picayune.MIT.EDU
  308. Xref: news.columbia.edu sci.crypt:21375 talk.politics.crypto:2943 sci.answers:900 news.answers:18266 talk.answers:150
  309.  
  310. Archive-name: cryptography-faq/part03
  311. Last-modified: 93/08/30
  312.  
  313.  
  314. This is the third of ten parts of the sci.crypt FAQ. The parts are
  315. mostly independent, but you should read the first part before the rest.
  316. We don't have the time to send out missing parts by mail, so don't ask.
  317. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  318.  
  319. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  320. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  321. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  322. sci.answers, and news.answers every 21 days.
  323.  
  324.  
  325. Contents:
  326.  
  327. 3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
  328. 3.2. What references can I start with to learn cryptology?
  329. 3.3. How does one go about cryptanalysis?
  330. 3.4. What is a brute-force search and what is its cryptographic relevance?
  331. 3.5. What are some properties satisfied by every strong cryptosystem?
  332. 3.6. If a cryptosystem is theoretically unbreakable, then is it
  333.   guaranteed analysis-proof in practice?
  334. 3.7. Why are many people still using cryptosystems that are
  335.   relatively easy to break?
  336. 3.8. What are the basic types of cryptanalytic `attacks'?
  337.  
  338.  
  339. 3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
  340.  
  341.   The story begins: When Julius Caesar sent messages to his trusted
  342.   acquaintances, he didn't trust the messengers. So he replaced every A
  343.   by a D, every B by a E, and so on through the alphabet. Only someone
  344.   who knew the ``shift by 3'' rule could decipher his messages.
  345.  
  346.   A cryptosystem or cipher system is a method of disguising messages so
  347.   that only certain people can see through the disguise. Cryptography is
  348.   the art of creating and using cryptosystems. Cryptanalysis is the art
  349.   of breaking cryptosystems---seeing through the disguise even when
  350.   you're not supposed to be able to. Cryptology is the study of both
  351.   cryptography and cryptanalysis.
  352.  
  353.   The original message is called a plaintext. The disguised message is
  354.   called a ciphertext. Encryption means any procedure to convert
  355.   plaintext into ciphertext. Decryption means any procedure to convert
  356.   ciphertext into plaintext.
  357.  
  358.   A cryptosystem is usually a whole collection of algorithms. The
  359.   algorithms are labelled; the labels are called keys. For instance,
  360.   Caesar probably used ``shift by n'' encryption for several different
  361.   values of n. It's natural to say that n is the key here.
  362.  
  363.   The people who are supposed to be able to see through the disguise are
  364.   called recipients. Other people are enemies, opponents, interlopers,
  365.   eavesdroppers, or third parties.
  366.  
  367. 3.2. What references can I start with to learn cryptology?
  368.  
  369.   For an introduction to technical matter, the survey articles given
  370.   in part 10 are the best place to begin as they are, in general,
  371.   concise, authored by competent people, and well written. However,
  372.   these articles are mostly concerned with cryptology as it has
  373.   developed in the last 50 years or so, and are more abstract and
  374.   mathematical than historical. The Codebreakers by Kahn [KAH67] is
  375.   encyclopedic in its history and technical detail of cryptology up
  376.   to the mid-60's.
  377.  
  378.   Introductory cryptanalysis can be learned from Gaines [GAI44] or
  379.   Sinkov [SIN66]. This is recommended especially for people who want
  380.   to devise their own encryption algorithms since it is a common
  381.   mistake to try to make a system before knowing how to break one.
  382.  
  383.   The selection of an algorithm for the DES drew the attention of
  384.   many public researchers to problems in cryptology. Consequently
  385.   several textbooks and books to serve as texts have appeared. The
  386.   book of Denning [DEN82] gives a good introduction to a broad range
  387.   of security including encryption algorithms, database security,
  388.   access control, and formal models of security. Similar comments
  389.   apply to the books of Price & Davies [PRI84] and Pfleeger [PFL89].
  390.  
  391.   The books of Konheim [KON81] and Meyer & Matyas [MEY82] are quite
  392.   technical books. Both Konheim and Meyer were directly involved in
  393.   the development of DES, and both books give a thorough analysis of
  394.   DES. Konheim's book is quite mathematical, with detailed analyses
  395.   of many classical cryptosystems. Meyer and Matyas concentrate on
  396.   modern cryptographic methods, especially pertaining to key management
  397.   and the integration of security facilities into computer systems and
  398.   networks. For more recent documentation on related areas, try
  399.   G. Simmons in [SIM91].
  400.  
  401.   The books of Rueppel [RUE86] and Koblitz [KOB89] concentrate on
  402.   the application of number theory and algebra to cryptography.
  403.  
  404. 3.3. How does one go about cryptanalysis?
  405.  
  406.   Classical cryptanalysis involves an interesting combination of
  407.   analytical reasoning, application of mathematical tools, pattern
  408.   finding, patience, determination, and luck. The best available
  409.   textbooks on the subject are the Military Cryptanalytics series
  410.   [FRIE1]. It is clear that proficiency in cryptanalysis is, for
  411.   the most part, gained through the attempted solution of given
  412.   systems. Such experience is considered so valuable that some of the
  413.   cryptanalyses performed during WWII by the Allies are still
  414.   classified.
  415.  
  416.   Modern public-key cryptanalysis may consist of factoring an integer,
  417.   or taking a discrete logarithm. These are not the traditional fare
  418.   of the cryptanalyst. Computational number theorists are some of the
  419.   most successful cryptanalysts against public key systems.
  420.  
  421. 3.4. What is a brute-force search and what is its cryptographic relevance?
  422.  
  423.   In a nutshell: If f(x) = y and you know y and can compute f, you can
  424.   find x by trying every possible x. That's brute-force search.
  425.  
  426.   Example: Say a cryptanalyst has found a plaintext and a corresponding
  427.   ciphertext, but doesn't know the key. He can simply try encrypting the
  428.   plaintext using each possible key, until the ciphertext matches---or
  429.   decrypting the ciphertext to match the plaintext, whichever is faster.
  430.   Every well-designed cryptosystem has such a large key space that this
  431.   brute-force search is impractical.
  432.     
  433.   Advances in technology sometimes change what is considered
  434.   practical. For example, DES, which has been in use for over 10 years
  435.   now, has 2^56, or about 10^17, possible keys. A computation with
  436.   this many operations was certainly unlikely for most users in the
  437.   mid-70's. The situation is very different today given the dramatic
  438.   decrease in cost per processor operation. Massively parallel
  439.   machines threaten the security of DES against brute force search.
  440.   Some scenarios are described by Garron and Outerbridge [GAR91].
  441.  
  442.   One phase of a more sophisticated cryptanalysis may involve a
  443.   brute-force search of some manageably small space of possibilities.
  444.  
  445. 3.5. What are some properties satisfied by every strong cryptosystem?
  446.  
  447.   The security of a strong system resides with the secrecy of the key
  448.   rather than with the supposed secrecy of the algorithm.
  449.  
  450.   A strong cryptosystem has a large keyspace, as mentioned above. It
  451.   has a reasonably large unicity distance; see question 8.8.
  452.  
  453.   A strong cryptosystem will certainly produce ciphertext which appears
  454.   random to all standard statistical tests (see, for example, [CAE90]).
  455.     
  456.   A strong cryptosystem will resist all known previous attacks. A
  457.   system which has never been subjected to scrutiny is suspect.
  458.  
  459.   If a system passes all the tests mentioned above, is it necessarily
  460.   strong? Certainly not. Many weak cryptosystems looked good at first.
  461.   However, sometimes it is possible to show that a cryptosystem is
  462.   strong by mathematical proof. ``If Joe can break this system, then
  463.   he can also solve the well-known difficult problem of factoring
  464.   integers.'' See part 6. Failing that, it's a crap shoot.
  465.  
  466. 3.6. If a cryptosystem is theoretically unbreakable, then is it
  467.   guaranteed analysis-proof in practice?
  468.  
  469.   Cryptanalytic methods include what is known as ``practical
  470.   cryptanalysis'': the enemy doesn't have to just stare at your
  471.   ciphertext until he figures out the plaintext. For instance, he might
  472.   assume ``cribs''---stretches of probable plaintext. If the crib is
  473.   correct then he might be able to deduce the key and then decipher the
  474.   rest of the message. Or he might exploit ``isologs''---the same
  475.   plaintext enciphered in several cryptosystems or several keys. Thus
  476.   he might obtain solutions even when cryptanalytic theory says he
  477.   doesn't have a chance.
  478.  
  479.   Sometimes, cryptosystems malfunction or are misused. The one-time pad,
  480.   for example, loses all security if it is used more than once! Even
  481.   chosen-plaintext attacks, where the enemy somehow feeds plaintext into
  482.   the encryptor until he can deduce the key, have been employed. See
  483.   [KAH67].
  484.   
  485. 3.7. Why are many people still using cryptosystems that are
  486.   relatively easy to break?
  487.  
  488.   Some don't know any better. Often amateurs think they can design
  489.   secure systems, and are not aware of what an expert cryptanalyst
  490.   could do. And sometimes there is insufficient motivation for anybody
  491.   to invest the work needed to crack a system.
  492.  
  493. 3.8. What are the basic types of cryptanalytic `attacks'?
  494.  
  495.   A standard cryptanalytic attack is to know some plaintext matching a
  496.   given piece of ciphertext and try to determine the key which maps one 
  497.   to the other.  This plaintext can be known because it is standard (a
  498.   standard greeting, a known header or trailer, ...) or because it is
  499.   guessed.  If text is guessed to be in a message, its position is probably
  500.   not known, but a message is usually short enough that the cryptanalyst
  501.   can assume the known plaintext is in each possible position and do
  502.   attacks for each case in parallel.  In this case, the known plaintext can
  503.   be something so common that it is almost guaranteed to be in a message.
  504.  
  505.   A strong encryption algorithm will be unbreakable not only under known
  506.   plaintext (assuming the enemy knows all the plaintext for a given
  507.   ciphertext) but also under "adaptive chosen plaintext" -- an attack
  508.   making life much easier for the cryptanalyst.  In this attack, the enemy
  509.   gets to choose what plaintext to use and gets to do this over and over,
  510.   choosing the plaintext for round N+1 only after analyzing the result of
  511.   round N.
  512.  
  513.   For example, as far as we know, DES is reasonably strong even under an
  514.   adaptive chosen plaintext attack (the attack Biham and Shamir used).  Of
  515.   course, we do not have access to the secrets of government cryptanalytic
  516.   services.  Still, it is the working assumption that DES is reasonably
  517.   strong under known plaintext and triple-DES is very strong under all
  518.   attacks.
  519.  
  520.   To summarize, the basic types of cryptanalytic attacks in order of
  521.   difficulty for the attacker, hardest first, are:
  522.  
  523.   cyphertext only: the attacker has only the encoded message from which 
  524.     to determine the plaintext, with no knowledge whatsoever of the
  525.     latter.
  526.  
  527.     A cyphertext only attack is usually presumed to be possible, and
  528.     a code's resistance to it is considered the basis of its 
  529.     cryptographic security.
  530.  
  531.   known plaintext: the attacker has the plaintext and corresponding 
  532.     cyphertext of an arbitrary message not of his choosing. The
  533.     particular message of the sender's is said to be `compromised'.
  534.  
  535.     In some systems, one known cyphertext-plaintext pair will 
  536.     compromise the overall system, both prior and subsequent
  537.     transmissions, and resistance to this is characteristic of a 
  538.     secure code.
  539.  
  540.   Under the following attacks, the attacker has the far less likely
  541.   or plausible ability to `trick' the sender into encrypting or 
  542.   decrypting arbitrary plaintexts or cyphertexts. Codes that resist 
  543.   these attacks are considered to have the utmost security.
  544.  
  545.   chosen plaintext: the attacker has the capability to find the 
  546.     cyphertext corresponding to an arbitrary plaintext message of his 
  547.     choosing.
  548.  
  549.   chosen cyphertext: the attacker can choose arbitrary cyphertext and
  550.     find the corresponding decrypted plaintext. This attack can show
  551.     in public key systems, where it may reveal the private key.
  552.  
  553.   adaptive chosen plaintext: the attacker can determine the cyphertext
  554.     of chosen plaintexts in an interactive or iterative process based on
  555.     previous results. This is the general name for a method of attacking 
  556.     product ciphers called `differential cryptanalysis'.
  557.  
  558.   The next part of the FAQ gives the mathematical detail behind the 
  559.   various types of cryptoanalytic attacks.
  560.  
  561.  
  562. Subject: Cryptography FAQ (04/10: Mathematical Cryptology)
  563.  
  564. Archive-name: cryptography-faq/part04
  565. Last-modified: 93/08/14
  566.  
  567. This is the fourth of ten parts of the sci.crypt FAQ. The parts are
  568. mostly independent, but you should read the first part before the rest.
  569. We don't have the time to send out missing parts by mail, so don't ask.
  570. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  571.  
  572. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  573. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  574. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  575. sci.answers, and news.answers every 21 days.
  576.  
  577.  
  578.  
  579. Contents:
  580.  
  581. 4.1. In mathematical terms, what is a private-key cryptosystem?
  582. 4.2. What is an attack?
  583. 4.3. What's the advantage of formulating all this mathematically?
  584. 4.4. Why is the one-time pad secure?
  585. 4.5. What's a ciphertext-only attack?
  586. 4.6. What's a known-plaintext attack?
  587. 4.7. What's a chosen-plaintext attack?
  588. 4.8. In mathematical terms, what can you say about brute-force attacks?
  589. 4.9. What's a key-guessing attack? What's entropy?
  590.  
  591.  
  592. Reader, beware: This section is highly mathematical. Well, maybe not
  593. _highly_ mathematical, but it's got a bunch of symbols and scary-looking
  594. formulas. You have been warned.
  595.  
  596.  
  597. 4.1. In mathematical terms, what is a private-key cryptosystem?
  598.  
  599.   A private-key cryptosystem consists of an encryption system E and a
  600.   decryption system D. The encryption system E is a collection of
  601.   functions E_K, indexed by ``keys'' K, mapping some set of
  602.   ``plaintexts'' P to some set of ``ciphertexts'' C. Similarly the
  603.   decryption system D is a collection of functions D_K such that
  604.   D_K(E_K(P)) = P for every plaintext P. That is, succesful decryption
  605.   of ciphertext into plaintext is accomplished using the same key
  606.   (index) as was used for the corresponding encryption of plaintext
  607.   into ciphertext. Such systems, where the same key value is used to
  608.   encrypt and decrypt, are also known as ``symmetric'' cryptoystems.
  609.  
  610. 4.2. What is an attack?
  611.  
  612.   In intuitive terms a (passive) attack on a cryptosystem is any method
  613.   of starting with some information about plaintexts and their
  614.   corresponding ciphertexts under some (unknown) key, and figuring out
  615.   more information about the plaintexts. It's possible to state
  616.   mathematically what this means. Here we go.
  617.  
  618.   Fix functions F, G, and H of n variables. Fix an encryption system E,
  619.   and fix a distribution of plaintexts and keys.
  620.  
  621.   An attack on E using G assuming F giving H with probability p is an
  622.   algorithm A with a pair f, g of inputs and one output h, such that
  623.   there is probability p of computing h = H(P_1,...,P_n), if we have
  624.   f = F(P_1,...,P_n) and g = G(E_K(P_1),...,E_K(P_n)). Note that this
  625.   probability depends on the distribution of the vector (K,P_1,...,P_n).
  626.  
  627.   The attack is trivial (or ``pointless'') if there is probability at
  628.   least p of computing h = H(P_1,...,P_n) if f = F(P_1,...,P_n) and
  629.   g = G(C_1,...,C_n). Here C_1,...,C_n range uniformly over the possible
  630.   ciphertexts, and have no particular relation to P_1,...,P_n. In other
  631.   words, an attack is trivial if it doesn't actually use the encryptions
  632.   E_K(P_1),...,E_K(P_n).
  633.  
  634.   An attack is called ``one-ciphertext'' if n = 1, ``two-ciphertext'' if
  635.   n = 2, and so on.
  636.  
  637. 4.3. What's the advantage of formulating all this mathematically?
  638.  
  639.   In basic cryptology you can never prove that a cryptosystem is secure.
  640.   Read part 3: we keep saying ``a strong cryptosystem must have this
  641.   property, but having this property is no guarantee that a cryptosystem
  642.   is strong!''
  643.  
  644.   In contrast, the purpose of mathematical cryptology is to precisely
  645.   formulate and, if possible, prove the statement that a cryptosystem is
  646.   strong. We say, for example, that a cryptosystem is secure against
  647.   all (passive) attacks if any nontrivial attack against the system (as
  648.   defined above) is too slow to be practical. If we can prove this
  649.   statement then we have confidence that our cryptosystem will resist
  650.   any (passive) cryptanalytic technique. If we can reduce this statement
  651.   to some well-known unsolved problem then we still have confidence that
  652.   the cryptosystem isn't easy to break.
  653.  
  654.   Other parts of cryptology are also amenable to mathematical
  655.   definition. Again the point is to explicitly identify what assumptions
  656.   we're making and prove that they produce the desired results. We can
  657.   figure out what it means for a particular cryptosystem to be used
  658.   properly: it just means that the assumptions are valid.
  659.  
  660.   The same methodology is useful for cryptanalysis too. The cryptanalyst
  661.   can take advantage of incorrect assumptions. Often he can try to
  662.   construct a proof of security for a system, see where the proof fails,
  663.   and use these failures as the starting points for his analysis.
  664.   
  665. 4.4. Why is the one-time pad secure?
  666.  
  667.   By definition, the one-time pad is a cryptosystem where the
  668.   plaintexts, ciphertexts, and keys are all strings (say byte strings)
  669.   of some length m, and E_K(P) is just the sum (let's say the exclusive
  670.   or) of K and P.
  671.  
  672.   It is easy to prove mathematically that there are _no_ nontrivial
  673.   single-ciphertext attacks on the one-time pad, assuming a uniform
  674.   distribution of keys. Note that we don't have to assume a uniform
  675.   distribution of plaintexts. (Here's the proof: Let A be an attack,
  676.   i.e., an algorithm taking two inputs f, g and producing one output h,
  677.   with some probability p that h = H(P) whenever f = F(P) and
  678.   g = G(E_K(P)) (i.e., g = G(K + P)). Then, because the distribution of
  679.   K is uniform and independent of P, the distribution of K + P must also
  680.   be uniform and independent of P. But also the distribution of C is
  681.   uniform and independent of P. Hence there is probability exactly p
  682.   that h = H(P) whenever f = F(P) and g = G(C), over all P and C. Thus
  683.   a fortiori A is trivial.)
  684.  
  685.   On the other hand the one-time pad is _not_ secure if a key K is used
  686.   for more than one plaintext: i.e., there are nontrivial
  687.   multiple-ciphertext attacks. So to be properly used a key K must be
  688.   thrown away after one encryption. The key is also called a ``pad'';
  689.   this explains the name ``one-time pad.''
  690.  
  691.   Also, a computer-based pseudo-random number generator does _not_ 
  692.   qualify as a true one-time pad because of its deterministic 
  693.   properties. See `pseudo-random number generators as key stream'.
  694.  
  695. 4.5. What's a ciphertext-only attack?
  696.  
  697.   In the notation above, a ciphertext-only attack is one where F is
  698.   constant. Given only some information G(E_K(P_1),...,E_K(P_n)) about
  699.   n ciphertexts, the attack has to have some chance of producing some
  700.   information H(P_1,...,P_n) about the plaintexts. The attack is trivial
  701.   if it has just as good a chance of producing H(P_1,...,P_n) when given
  702.   G(C_1,...,C_n) for random C_1,...,C_n.
  703.  
  704.   For example, say G(C) = C, and say H(P) is the first bit of P. We can
  705.   easily write down an attack---the ``guessing attack,'' which simply
  706.   guesses that H(P) is 1. This attack is trivial because it doesn't use
  707.   the ciphertext: it has a fifty-fifty chance of guessing correctly no
  708.   matter what. On the other hand there is an attack on RSA which
  709.   produces one bit of information about P, with 100% success, using C.
  710.   If it is fed a random C then the success rate drops to 50%. So this is
  711.   a nontrivial attack.
  712.  
  713. 4.6. What's a known-plaintext attack?
  714.  
  715.   The classic known-plaintext attack has F(P_1,P_2) = P_1,
  716.   G(C_1,C_2) = (C_1,C_2), and H(P_1,P_2) depending only on P_2.
  717.   In other words, given two ciphertexts C_1 and C_2 and one decryption
  718.   P_1, the known-plaintext attack should produce information about the
  719.   other decryption P_2.
  720.  
  721.   Note that known-plaintext attacks are often defined in the literature
  722.   as producing information about the key, but this is pointless: the
  723.   cryptanalyst generally cares about the key only insofar as it lets him
  724.   decrypt further messages.
  725.  
  726. 4.7. What's a chosen-plaintext attack?
  727.  
  728.   A chosen-plaintext attack is the first of an increasingly impractical
  729.   series of _active_ attacks on a cryptosystem: attacks where the
  730.   cryptanalyst feeds data to the encryptor. These attacks don't fit into
  731.   our model of passive attacks explained above. Anyway, a
  732.   chosen-plaintext attack lets the cryptanalyst choose a plaintext and
  733.   look at the corresponding ciphertext, then repeat until he has figured
  734.   out how to decrypt any message. More absurd examples of this sort of
  735.   attack are the ``chosen-key attack'' and ``chosen-system attack.''
  736.  
  737.   A much more important form of active attack is a message corruption
  738.   attack, where the attacker tries to change the ciphertext in such a
  739.   way as to make a useful change in the plaintext.
  740.  
  741.   There are many easy ways to throw kinks into all of these attacks:
  742.   for instance, automatically encrypting any plaintext P as
  743.   T,E_K(h(T+R+P),R,P), where T is a time-key (sequence number) chosen anew
  744.   for each message, R is a random number, and h is a one-way hash
  745.   function. Here comma means concatenation and plus means exclusive-or.
  746.  
  747. 4.8. In mathematical terms, what can you say about brute-force attacks?
  748.  
  749.   Consider the following known-plaintext attack. We are given some
  750.   plaintexts P_1,...,P_{n-1} and ciphertexts C_1,...,C_{n-1}. We're
  751.   also given a ciphertext C_n. We run through every key K. When we find
  752.   K such that E_K(P_i) = C_i for every i < n, we print D_K(C_n).
  753.  
  754.   If n is big enough that only one key works, this attack will succeed
  755.   on valid inputs all the time, while it will produce correct results
  756.   only once in a blue moon for random inputs. Thus this is a nontrivial
  757.   attack. Its only problem is that it is very slow if there are many
  758.   possible keys.
  759.  
  760. 4.9. What's a key-guessing attack? What's entropy?
  761.  
  762.   Say somebody is using the one-time pad---but isn't choosing keys
  763.   randomly and uniformly from all m-bit messages, as he was supposed to
  764.   for our security proof. In fact say he's known to prefer keys which
  765.   are English words. Then a cryptanalyst can run through all English
  766.   words as possible keys. This attack will often succeed, and it's much
  767.   faster than a brute-force search of the entire keyspace.
  768.  
  769.   We can measure how bad a key distribution is by calculating its
  770.   entropy. This number E is the number of ``real bits of information''
  771.   of the key: a cryptanalyst will typically happen across the key within
  772.   2^E guesses. E is defined as the sum of -p_K log_2 p_K, where p_K is
  773.   the probability of key K.
  774.  
  775.  
  776. Subject: Cryptography FAQ (05/10: Product Ciphers)
  777.  
  778. Archive-name: cryptography-faq/part05
  779. Last-modified: 93/08/14
  780.  
  781.  
  782. This is the fifth of ten parts of the sci.crypt FAQ. The parts are
  783. mostly independent, but you should read the first part before the rest.
  784. We don't have the time to send out missing parts by mail, so don't ask.
  785. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  786.  
  787. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  788. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  789. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  790. sci.answers, and news.answers every 21 days.
  791.  
  792.  
  793.  
  794. Contents:
  795.  
  796. 5.1. What is a product cipher?
  797. 5.2. What makes a product cipher secure?
  798. 5.3. What are some group-theoretic properties of product ciphers?
  799. 5.4. What can be proven about the security of a product cipher?
  800. 5.5. How are block ciphers used to encrypt data longer than the block size?
  801. 5.6. Can symmetric block ciphers be used for message authentication?
  802. 5.7. What exactly is DES?
  803. 5.8. What is triple DES?
  804. 5.9. What is differential cryptanalysis?
  805. 5.10. How was NSA involved in the design of DES?
  806. 5.11. Is DES available in software?
  807. 5.12. Is DES available in hardware?
  808. 5.13. Can DES be used to protect classified information?
  809. 5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption?
  810.  
  811.  
  812. 5.1. What is a product cipher?
  813.  
  814.   A product cipher is a block cipher that iterates several weak
  815.   operations such as substitution, transposition, modular
  816.   addition/multiplication, and linear transformation. (A ``block
  817.   cipher'' just means a cipher that encrypts a block of data---8 bytes,
  818.   say---all at once, then goes on to the next block.) The notion of
  819.   product ciphers is due to Shannon [SHA49]. Examples of modern
  820.   product ciphers include LUCIFER [SOR84], DES [NBS77], SP-networks
  821.   [KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu and Khafre
  822.   [ME91a]. The so-called Feistel ciphers are a class of product
  823.   ciphers which operate on one half of the ciphertext at each round,
  824.   and then swap the ciphertext halves after each round. LUCIFER,
  825.   DES, LOKI, and FEAL are examples of Feistel ciphers.
  826.  
  827.   The following table compares the main parameters of several product 
  828.   ciphers:
  829.  
  830.   cipher   |   block length   |   key bits   |   number of rounds
  831.   LUCIFER          128               128                16
  832.   DES               64                56                16
  833.   LOKI              64                64                16
  834.   FEAL              64               128            2^x, x >= 5
  835.   PES               64               128                 8
  836.  
  837. 5.2. What makes a product cipher secure?
  838.  
  839.   Nobody knows how to prove mathematically that a product cipher is
  840.   completely secure. So in practice one begins by demonstrating that the
  841.   cipher ``looks highly random''. For example, the cipher must be
  842.   nonlinear, and it must produce ciphertext which functionally depends
  843.   on every bit of the plaintext and the key. Meyer [MEY78] has shown
  844.   that at least 5 rounds of DES are required to guarantee such a
  845.   dependence. In this sense a product cipher should act as a ``mixing''
  846.   function which combines the plaintext, key, and ciphertext in a
  847.   complex nonlinear fashion.
  848.  
  849.   The fixed per-round substitutions of the product cipher are
  850.   referred to as S-boxes. For example, LUCIFER has 2 S-boxes, and DES
  851.   has 8 S-boxes. The nonlinearity of a product cipher reduces to a
  852.   careful design of these S-boxes. A list of partial design criteria
  853.   for the S-boxes of DES, which apply to S-boxes in general, may be
  854.   found in Brown [BRO89] and Brickell et al. [BRI86].
  855.  
  856. 5.3. What are some group-theoretic properties of product ciphers?
  857.  
  858.   Let E be a product cipher that maps N-bit blocks to N-bit blocks.
  859.   Let E_K(X) be the encryption of X under key K. Then, for any fixed K,
  860.   the map sending X to E_K(X) is a permutation of the set of N-bit
  861.   blocks. Denote this permutation by P_K. The set of all N-bit
  862.   permutations is called the symmetric group and is written S_{2^N}.
  863.   The collection of all these permutations P_K, where K ranges over all
  864.   possible keys, is denoted E(S_{2^N}). If E were a random mapping from
  865.   plaintexts to ciphertexts then we would expect E(S_{2^N}) to generate
  866.   a large subset of S_{2^N}.
  867.  
  868.   Coppersmith and Grossman [COP74] have shown that a very simple
  869.   product cipher can generate the alternating group A_{2^N} given a
  870.   sufficient number of rounds. (The alternating group is half of the
  871.   symmetric group: it consists of all ``even'' permutations, i.e., all
  872.   permutations which can be written as an even number of swaps.)
  873.   Even and Goldreich [EVE83] were able to extend these results to show
  874.   that Feistel ciphers can generate A_{2^N}, given a sufficient number
  875.   of rounds.
  876.  
  877.   The security of multiple encipherment also depends on the
  878.   group-theoretic properties of a cipher. Multiple encipherment is an
  879.   extension over single encipherment if for keys K1, K2 there does
  880.   not exist a third key K3 such that
  881.  
  882.   E_K2(E_K1(X)) == E_(K3)(X)                (**)
  883.  
  884.   which indicates that encrypting twice with two independent keys
  885.   K1, K2 is equal to a single encryption under the third key K3. If
  886.   for every K1, K2 there exists a K3 such that eq. (**) is true then
  887.   we say that E is a group.
  888.  
  889.   This question of whether DES is a group under this definition was
  890.   extensively studied by Sherman, Kaliski, and Rivest [SHE88]. In their
  891.   paper they give strong evidence for the hypothesis that DES is not a
  892.   group. In fact DES is not a group [CAM93].
  893.  
  894. 5.4. What can be proven about the security of a product cipher?
  895.  
  896.   Recall from above that P_K is a permutation produced by E under
  897.   some key K. The goal of the designer of E is to ensure that P_K
  898.   appears to be a random element of S_{2^N}, the symmetric group.
  899.   Let R be an element of S_{2^N} selected randomly. We will say that P_K
  900.   and R are indistinguishable if an observer given P_K and R in some
  901.   order cannot distinguish between these two permutations in polynomial
  902.   time. That is, with time bounded resources, the observer cannot
  903.   determine which of the permutations is produced by E: the optimal
  904.   decision is no better than simply guessing.
  905.  
  906.   Luby and Rackoff [LUB88] have shown that a class of Feistel ciphers
  907.   are secure in this sense when the round mapping is replaced by
  908.   random boolean functions.
  909.  
  910. 5.5. How are block ciphers used to encrypt data longer than the block size?
  911.  
  912.   There are four standard ``modes of operation'' (and numerous non-standard
  913.   ones as well). The standard modes of operation are defined in the U.S.
  914.   Department of Commerce Federal Information Processing Standard (FIPS) 81,
  915.   published in 1980. See the question about ECB below for more details.
  916.  
  917.   Although they are defined for the DES block cipher, the ``modes of
  918.   operation'' can be used with any block cipher.
  919.  
  920. 5.6. Can symmetric block ciphers be used for message authentication?
  921.  
  922.   You may use a symmetric cryptosystem block cipher to prove to yourself
  923.   that you generated a message, and that the message wasn't altered
  924.   after you created it. But you cannot prove these things to anyone else
  925.   without revealing your key. Thereafter you cannot prove anything about
  926.   messages authenticated with that key.
  927.   
  928.   See ANSI X3.106-1983 and FIPS 113 (1985) for a standard method of message
  929.   authentication using DES.
  930.  
  931. 5.7. What exactly is DES?
  932.  
  933.   DES is the U.S. Government's Data Encryption Standard, a product 
  934.   cipher that operates on 64-bit blocks of data, using a 56-bit key. 
  935.  
  936.   It is defined in FIPS 46-1 (1988) [which supersedes FIPS 46 (1977)].
  937.   FIPS are Federal Information Processing Standards published by NTIS.
  938.   DES is identical to the ANSI standard Data Encryption Algorithm (DEA)
  939.   defined in ANSI X3.92-1981. 
  940.  
  941. 5.8. What is triple DES?
  942.  
  943.   Triple DES is a product cipher which, like DES, operates on 64-bit 
  944.   data blocks. There are several forms, each of which uses the DES
  945.   cipher 3 times. Some forms use two 56-bit keys, some use three.
  946.   The DES ``modes of operation'' may also be used with triple-DES.
  947.  
  948.   Some people refer to E(K1,D(K2,E(K1,x))) as triple-DES.
  949.  
  950.   This method is defined in chapter 7.2 of the ANSI standard X9.17-1985
  951.   ``Financial Institution Key Management'' and is intended for use in
  952.   encrypting DES keys and IVs for ``Automated Key Distribution''. Its
  953.   formal name is ``Encryption and Decryption of a Single Key by a Key
  954.   Pair'', but it is referenced in other standards documents as EDE.
  955.  
  956.   That standard says (section 7.2.1): ``Key encrypting keys may be a single
  957.   DEA key or a DEA key pair. Key pairs shoud be used where additional
  958.   security is needed (e.g., the data protected by the key(s) has a long
  959.   security life). A key pair shall not be encrypted or decrypted using a
  960.   single key.''
  961.  
  962.   Others use the term ``triple-DES'' for E(K1,D(K2,E(K3,x))) or
  963.   E(K1,E(K2,E(K3,x))).
  964.  
  965.   Carl Ellison advocates triple DES use in the form
  966.  
  967.     E(K1, Tran( E(K2, Tran( E(K3, Compress( x )))))),
  968.  
  969.   where each DES instance has its own key and IV (for CBC mode) and Tran
  970.   is a large-block transposition program. Tran is available from [FTPTR].
  971.  
  972. 5.9. What is differential cryptanalysis?
  973.  
  974.   Differential cryptanalysis is a statistical attack that can be
  975.   applied to any iterated mapping (i.e., any mapping which is based on
  976.   a repeated round function). The method was recently popularized by
  977.   Biham and Shamir [BIH91], but Coppersmith has remarked that the
  978.   S-boxes of DES were optimized against this attack some 20 years ago.
  979.   This method has proved effective against several product ciphers,
  980.   notably FEAL [BI91a].
  981.  
  982.   Differential cryptanalysis is based on observing a large number of
  983.   ciphertexts Y, Y' whose corresponding plaintexts X, X' satisfy a
  984.   known difference D = X+X', where + is componentwise XOR. In the
  985.   basic Biham-Shamir attack, 2^{47} such plaintext pairs are required
  986.   to determine the key for DES. Substantially fewer pairs are required
  987.   if DES is truncated to 6 or 8 rounds. In these cases, the actual key
  988.   can be recovered in a matter of minutes using a few thousand pairs.
  989.   For full DES this attack is impractical because it requires so many
  990.   known plaintexts.
  991.  
  992.   The work of Biham and Shamir on DES revealed several startling
  993.   observations on the algorithm. Most importantly, if the key
  994.   schedule was removed from DES and a 16*48 = 768-bit key was used,
  995.   the key could be recovered in less than 2^{64} steps. Thus
  996.   independent subkeys do not add substantial security to DES.
  997.   Further, the S-boxes of DES are extremely sensitive in that
  998.   changing even single entries in these tables yields significant
  999.   improvement in the differential attack.
  1000.  
  1001.   Adi Shamir is quoted to say (NYTimes Oct 13 1991), ``I would say
  1002.   that, contrary to what some people believe, there is no evidence
  1003.   of tampering with the DES so that the basic design was weakened.''
  1004.  
  1005. 5.10. How was NSA involved in the design of DES?
  1006.  
  1007.   According to Kinnucan [KIN78], Tuchman, a member of the group that
  1008.   developed DES at IBM is quoted as saying, ``We developed the DES
  1009.   algorithm entirely within IBM using IBMers. The NSA did not
  1010.   dictate a single wire!'' Tuchman and Meyer (another developer of
  1011.   DES) spent a year breaking ciphers and finding weaknesses in
  1012.   Lucifer. They then spent two years strengthening Lucifer. ``Their
  1013.   basic approach was to look for strong substitution, permutation,
  1014.   and key scheduling functions ... IBM has classified the notes
  1015.   containing the selection criteria at the request of the NSA....
  1016.   `The NSA told us we had inadvertently reinvented some of the deep
  1017.   secrets it uses to make its own algorithms,' explains Tuchman.''
  1018.   
  1019.   On the other hand, a document called ``Involvement of the NSA in
  1020.   the development of DES: unclassified summary of the United States
  1021.   Select Committee on Intelligence'', printed in the IEEE
  1022.   Communications Magazine, p53-55, 1978, states: ``In the development
  1023.   of DES, NSA convinced IBM that a reduced keysize was sufficient;
  1024.   indirectly assisted in the development of the S-box structures; and
  1025.   certified that the final DES algorithm was, to the best of their
  1026.   knowledge, free from any statistical or mathematical weakness.''
  1027.  
  1028.   Clearly the key size was reduced at the insistence of the NSA.
  1029.   The article further states that the NSA did not tamper with the
  1030.   algorithm itself, just the parameters, which in some sense
  1031.   resolves the apparent conflict in the remarks of Meyer and Tuchman
  1032.   presented above.
  1033.  
  1034. 5.11. Is DES available in software?
  1035.  
  1036.   Several people have made DES code available via ftp (see part 10 for
  1037.   pathnames): Stig Ostholm [FTPSO]; BSD [FTPBK]; Eric Young [FTPEY];
  1038.   Dennis Furguson [FTPDF]; Mark Riordan [FTPMR]; Phil Karn [FTPPK].
  1039.   A Pascal listing of DES is also given in Patterson [PAT87]. Antti 
  1040.   Louko <alo@kampi.hut.fi> has written a version of DES with BigNum
  1041.   packages in [FTPAL].
  1042.  
  1043.   FIPS 46-1 says ``The algorithm specified in this standard is to be
  1044.   implemented ... using hardware (not software) technology. ...
  1045.   Software implementations in general purpose computers are not in
  1046.   compliance with this standard.''  Despite this, software
  1047.   implementations abound, and are used by government agencies.
  1048.  
  1049. 5.12. Is DES available in hardware?
  1050.  
  1051.   The following paragraphs are quoted from messages sent to the editors.
  1052.   We don't vouch for the quality or even existence of the products.
  1053.  
  1054.   Chip Rosenthal says: ``Dallas Semiconductor makes a DES
  1055.   encryption/decryption device for use on standard, digital 64Kbps PCM
  1056.   telecom data streams. It is capable of processing data in real time,
  1057.   e.g. one sample/frame. It is the DS2160. Their phone number is
  1058.   214-450-0400. You would probably need to talk with Dewight in Telecom
  1059.   marketing.''
  1060.  
  1061.   Christian Franke, franke@informatik.rwth-aachen.de, says: ``1.
  1062.   Cryptech CRY12C102: 22.5Mbit/s according to Data Sheet, with 32 Bit
  1063.   interface. We use this one, because it was the only one available when
  1064.   we started the project. No problems !  2. Pijnenburg PCC100: 20Mbit/s
  1065.   according to Data Sheet. Address: PIJNENBURG B.V., Boxtelswweg 26,
  1066.   NL-5261 NE Vught, The Netherlands. 3. INFOSYS DES Chip (Germany):
  1067.   S-Boxes must be loaded by software. So you can modify the Algorithm.
  1068.   Sorry, I don't have the data sheet handy. Please E-Mail me if you need
  1069.   further information.''
  1070.  
  1071.   Marcus J Ranum, mjr@tis.com, says: ``SuperCrypt'' 100Mb/sec and faster
  1072.   DES and Proprietary Storage for 16 56-bit keys Key stream generator
  1073.   Integrated hardware DES3 procedure Extended mode with 112 bit keys;
  1074.   Computer Elektronik Infosys; 512-A Herndon Parkway,; Herndon, VA
  1075.   22070; 800-322-3464.
  1076.  
  1077.   Tim Hember, thember@gandalf.ca, says: Newbridge Microsystems sells
  1078.   an AM9568 compatible DES chip that operates at 25MHz, performs a
  1079.   round of encryption in 18 clocks, has a three-stage pipeline,
  1080.   supports ECB, CBC, CFB-8 and >>> CFB-1 <<<<. Further it is very
  1081.   reasonable priced as opposed to other high-end DES chips. Call
  1082.   Newbridge Microsystems, Ottawa, 613-592-0714. (... there are no
  1083.   import/export issues with Canada and the US). If you require custom
  1084.   DES or Public Key ICs then Timestep Engineering developed
  1085.   Newbridge's crypto chips and ICs for other commercial and
  1086.   educational establishments. They can be reached at 613-820-0024.
  1087.  
  1088. 5.13. Can DES be used to protect classified information?
  1089.  
  1090.   DES is not intended to protect classified data. FIPS 46-1 says:
  1091.   ``This standard will be used by Federal departments and agencies for
  1092.   the cryptographic protection of computer data when the following
  1093.   conditions apply: 1. ... cryptographic protection is required; and
  1094.   2. the data is not classified according to the National Security Act
  1095.   of 1947, as amended, or the Atomic Energy Act of 1954, as amended.''
  1096.  
  1097. 5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption?
  1098.  
  1099.   These are methods for using block ciphers, such as DES, to encrypt 
  1100.   messages, files, and blocks of data, known as ``modes of operation.''
  1101.   Four ``modes of operation'' are defined in FIPS 81 (1980 December 2), 
  1102.   and also in ANSI X3.106-1983. 
  1103.  
  1104.   FIPS 81 specifies that when 7-bit ASCII data is sent in octets, the
  1105.   unused most-significant bit is to be set to 1.
  1106.  
  1107.   FIPS 81 also specifies the padding for short blocks.
  1108.  
  1109.   The four FIPS/ANSI standard DES modes of operation are: 
  1110.         Electronic Code Book  (ECB), 
  1111.         Cipher Block Chaining (CBC), 
  1112.         K-bit Cipher FeedBack (CFB), and 
  1113.         K-bit Output FeedBack (OFB).
  1114.  
  1115.   All four of the ANSI/FIPS modes have very little "error extension".
  1116.   For a single bit error in the cipherstream, none of them produce an
  1117.   error burst in the decrypted output stream of longer than 128 bits.
  1118.  
  1119.   A fifth mode of operation, used in Kerberos and elsewhere but not
  1120.   defined in any standard, is error-Propagating Cipher Block Chaining 
  1121.   (PCBC).  Unlike the 4 standard modes, PCBC extends or propagates the
  1122.   effect of a single bit error in the cipherstream throughout remainder 
  1123.   of the decrypted textstream after the point of error.
  1124.  
  1125.   These 5 methods are explained below in a C-language-like notation.
  1126.  
  1127.   Some symbols:
  1128.  
  1129.   P[n]  The n'th block of plaintext, input to encryption, output from
  1130.         decryption. Size of block determined by the mode.
  1131.  
  1132.   C[n]  The n'th block of ciphertext, output from encryption, input to
  1133.         decryption. Size of block determined by the mode.
  1134.  
  1135.   E(m)  The DES encryption function, performed on 64-bit block m, using
  1136.         the 16-key schedule derived from some 56-bit key.
  1137.  
  1138.   D(m)  The DES decryption function, performed on 64-bit block m, using
  1139.         the same key schedule as in E(m), except that the 16 keys
  1140.         in the schedule are used in the opposite order as in E(m).
  1141.  
  1142.   IV    A 64-bit ``initialization vector'', a secret value which, along with
  1143.         the key, is shared by both encryptor and decryptor.
  1144.  
  1145.   I[n]  The n'th value of a 64-bit variable, used in some modes.
  1146.   R[n]  The n'th value of a 64-bit variable, used in some modes.
  1147.  
  1148.   LSB(m,k) The k least significant (right-most) bits of m.
  1149.         e.g. m & ((1 << k) - 1)
  1150.  
  1151.   MSB(m,k) The k most significant (left-most) bits of m.
  1152.         e.g. (m >> (64-k)) & ((1 << k) - 1)
  1153.  
  1154.   = ^ << >> &  operators as defined in the c langage.
  1155.  
  1156.  
  1157.   Electronic Code Book (ECB):
  1158.  
  1159.           P[n] and C[n] are each 64-bits long.
  1160.  
  1161.           Encryption:                   Decryption:
  1162.           C[n] = E(P[n])                P[n] = D(C[n])
  1163.  
  1164.  
  1165.   Cipher Block Chaining (CBC):
  1166.  
  1167.           P[n] and C[n] are each 64-bits long.
  1168.  
  1169.           Encryption:                   Decryption:
  1170.           C[0] = E(P[0]^IV)             P[0] = D(C[0])^IV
  1171.   (n>0)   C[n] = E(P[n]^C[n-1])         P[n] = D(C[n])^C[n-1]
  1172.  
  1173.  
  1174.   Propagating Cipher Block Chaining (PCBC):
  1175.  
  1176.           P[n] and C[n] are each 64-bits long.
  1177.  
  1178.           Encryption:                   Decryption:
  1179.           C[0] = E(P[0]^IV)             P[0] = D(C[0])^IV
  1180.   (n>0)   C[n] = E(P[n]^P[n-1]^C[n-1])  P[n] = D(C[n])^P[n-1]^C[n-1]
  1181.  
  1182.  
  1183.   k-bit Cipher FeedBack (CFB):
  1184.  
  1185.           P[n] and C[n] are each k bits long, 1 <= k <= 64. 
  1186.  
  1187.           Encryption:                   Decryption:
  1188.           I[0] = IV                     I[0] = IV
  1189.   (n>0)   I[n] = I[n-1]<<k | C[n-1]     I[n] = I[n-1]<<k | C[n-1]       
  1190.   (all n) R[n] = MSB(E(I[n]),k)         R[n] = MSB(E(I[n]),k)
  1191.   (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]
  1192.  
  1193.           Note that for k==64, this reduces to:
  1194.  
  1195.           I[0] = IV                     I[0] = IV
  1196.   (n>0)   I[n] = C[n-1]                 I[n] = C[n-1]   
  1197.   (all n) R[n] = E(I[n])                R[n] = E(I[n])
  1198.   (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]
  1199.  
  1200.   CFB notes: Since I[n] depends only on the plain or cipher text from the
  1201.   previous operation, the E() function can be performed in parallel with
  1202.   the reception of the text with which it is used.
  1203.  
  1204.  
  1205.   k-bit Output FeedBack (OFB):
  1206.  
  1207.           P[n] and C[n] are each k bits long, 1 <= k <= 64. 
  1208.  
  1209.           Encryption:                   Decryption:
  1210.           I[0] = IV                     I[0] = IV
  1211.   (n>0)   I[n] = I[n-1]<<k | R[n-1]     I[n] = I[n-1]<<k | R[n-1]       
  1212.   (all n) R[n] = MSB(E(I[n]),k)         R[n] = MSB(E(I[n]),k)
  1213.   (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]
  1214.  
  1215.           Note that for k==64, this reduces to:
  1216.  
  1217.           I[0] = IV                     I[0] = IV
  1218.   (n>0)   I[n] = R[n-1]                 I[n] = R[n-1]   
  1219.   (all n) R[n] = E(I[n])                R[n] = E(I[n])
  1220.   (all n) C[n] = P[n]^R[n]              P[n] = C[n]^R[n]
  1221.  
  1222.   OFB notes: encryption and decryption are identical. Since I[n] is
  1223.   independent of P and C, the E() function can be performed in advance of
  1224.   the receipt of the plain/cipher text with which it is to be used.
  1225.  
  1226.  
  1227.   Additional notes on DES ``modes of operation'':
  1228.  
  1229.   ECB and CBC use E() to encrypt and D() to decrypt, but the feedback
  1230.   modes use E() to both encrypt and decrypt. This disproves the following 
  1231.   erroneous claim: ``DES implementations which provide E() but not D()
  1232.   cannot be used for data confidentiality.''
  1233.  
  1234.  
  1235.  
  1236. Subject: Cryptography FAQ (06/10: Public Key Cryptography)
  1237.  
  1238. Archive-name: cryptography-faq/part06
  1239. Last-modified: 93/08/23
  1240.  
  1241.  
  1242. This is the sixth of ten parts of the sci.crypt FAQ. The parts are
  1243. mostly independent, but you should read the first part before the rest.
  1244. We don't have the time to send out missing parts by mail, so don't ask.
  1245. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  1246.  
  1247. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  1248. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  1249. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  1250. sci.answers, and news.answers every 21 days.
  1251.  
  1252.  
  1253.  
  1254. Contents:
  1255.  
  1256. 6.1. What is public-key cryptography?
  1257. 6.2. How does public-key cryptography solve cryptography's Catch-22?
  1258. 6.3. What is the role of the `trapdoor function' in public key schemes?
  1259. 6.4. What is the role of the `session key' in public key schemes?
  1260. 6.5. What's RSA?
  1261. 6.6. Is RSA secure?
  1262. 6.7. What's the difference between the RSA and Diffie-Hellman schemes?
  1263. 6.8. What is `authentication' and the `key distribution problem'?
  1264. 6.9. How fast can people factor numbers?
  1265. 6.10. What about other public-key cryptosystems?
  1266. 6.11. What is the `RSA Factoring Challenge?'
  1267.  
  1268.  
  1269. 6.1. What is public-key cryptography?
  1270.  
  1271.   In a classic cryptosystem, we have encryption functions E_K and
  1272.   decryption functions D_K such that D_K(E_K(P)) = P for any plaintext
  1273.   P. In a public-key cryptosystem, E_K can be easily computed from some
  1274.   ``public key'' X which in turn is computed from K. X is published, so
  1275.   that anyone can encrypt messages. If decryption D_K cannot be easily 
  1276.   computed from public key X without knowledge of private key K, but 
  1277.   readily with knowledge of K, then only the person who generated K can 
  1278.   decrypt messages. That's the essence of public-key cryptography, 
  1279.   introduced by Diffie and Hellman in 1976. 
  1280.   
  1281.   This document describes only the rudiments of public key cryptography.
  1282.   There is an extensive literature on security models for public-key 
  1283.   cryptography, applications of public-key cryptography, other 
  1284.   applications of the mathematical technology behind public-key 
  1285.   cryptography, and so on; consult the references at the end for more 
  1286.   refined and thorough presentations.
  1287.  
  1288. 6.2. How does public-key cryptography solve cryptography's Catch-22?
  1289.  
  1290.   In a classic cryptosystem, if you want your friends to be able to
  1291.   send secret messages to you, you have to make sure nobody other than
  1292.   them sees the key K. In a public-key cryptosystem, you just publish 
  1293.   X, and you don't have to worry about spies. Hence public key 
  1294.   cryptography `solves' one of the most vexing problems of all prior 
  1295.   cryptography: the necessity of establishing a secure channel for the 
  1296.   exchange of the key. To establish a secure channel one uses 
  1297.   cryptography, but private key cryptography requires a secure channel! 
  1298.   In resolving the dilemma, public key cryptography has been considered 
  1299.   by many to be a `revolutionary technology,' representing a 
  1300.   breakthrough that makes routine communication encryption practical 
  1301.   and potentially ubiquitous.
  1302.  
  1303. 6.3. What is the role of the `trapdoor function' in public key schemes?
  1304.   
  1305.   Intrinsic to public key cryptography is a `trapdoor function' D_K 
  1306.   with the properties that computation in one direction (encryption, 
  1307.   E_K) is easy and in the other is virtually impossible (attack,
  1308.   determining P from encryption E_K(P) and public key X). Furthermore, 
  1309.   it has the special property that the reversal of the computation 
  1310.   (decryption, D_K) is again tractable if the private key K is known.
  1311.  
  1312. 6.4. What is the role of the `session key' in public key schemes?
  1313.  
  1314.   In virtually all public key systems, the encryption and decryption 
  1315.   times are very lengthy compared to other block-oriented 
  1316.   algorithms such as DES for equivalent data sizes. Therefore in most
  1317.   implementations of public-key systems, a temporary, random `session 
  1318.   key' of much smaller length than the message is generated for each 
  1319.   message and alone encrypted by the public key algorithm. The message 
  1320.   is actually encrypted using a faster private key algorithm with the 
  1321.   session key. At the receiver side, the session key is decrypted using 
  1322.   the public-key algorithms and the recovered `plaintext' key is used 
  1323.   to decrypt the message.
  1324.   
  1325.   The session key approach blurs the distinction between `keys' and 
  1326.   `messages' -- in the scheme, the message includes the key, and the 
  1327.   key itself is treated as an encryptable `message'. Under this 
  1328.   dual-encryption approach, the overall cryptographic strength is 
  1329.   related to the security of either the public- and private-key 
  1330.   algorithms.
  1331.  
  1332. 6.5. What's RSA?
  1333.  
  1334.   RSA is a public-key cryptosystem defined by Rivest, Shamir, and
  1335.   Adleman. Here's a small example. See also [FTPDQ].
  1336.  
  1337.   Plaintexts are positive integers up to 2^{512}. Keys are quadruples
  1338.   (p,q,e,d), with p a 256-bit prime number, q a 258-bit prime number,
  1339.   and d and e large numbers with (de - 1) divisible by (p-1)(q-1). We
  1340.   define E_K(P) = P^e mod pq, D_K(C) = C^d mod pq. All quantities are
  1341.   readily computed from classic and modern number theoretic algorithms 
  1342.   (Euclid's algorithm for computing the greatest common divisor yields
  1343.   an algorithm for the former, and historically newly explored
  1344.   computational approaches to finding large `probable' primes, such as 
  1345.   the Fermat test, provide the latter.)
  1346.  
  1347.   Now E_K is easily computed from the pair (pq,e)---but, as far as
  1348.   anyone knows, there is no easy way to compute D_K from the pair
  1349.   (pq,e). So whoever generates K can publish (pq,e). Anyone can send a
  1350.   secret message to him; he is the only one who can read the messages.
  1351.  
  1352. 6.6. Is RSA secure?
  1353.  
  1354.   Nobody knows. An obvious attack on RSA is to factor pq into p and q.
  1355.   See below for comments on how fast state-of-the-art factorization
  1356.   algorithms run. Unfortunately nobody has the slightest idea how to
  1357.   prove that factorization---or any realistic problem at all, for that
  1358.   matter---is inherently slow. It is easy to formalize what we mean by
  1359.   ``RSA is/isn't strong''; but, as Hendrik W. Lenstra, Jr., says,
  1360.   ``Exact definitions appear to be necessary only when one wishes to
  1361.   prove that algorithms with certain properties do _not_ exist, and
  1362.   theoretical computer science is notoriously lacking in such negative
  1363.   results.''
  1364.  
  1365.   Note that there may even be a `shortcut' to breaking RSA other than
  1366.   factoring. It is obviously sufficient but so far not provably 
  1367.   necessary. That is, the security of the system depends on two 
  1368.   critical assumptions: (1) factoring is required to break the system,
  1369.   and (2) factoring is `inherently computationally intractable',
  1370.   or, alternatively, `factoring is hard' and `any approach that can 
  1371.   be used to break the system is at least as hard as factoring'.
  1372.  
  1373.   Historically even professional cryptographers have made mistakes
  1374.   in estimating and depending on the intractability of various 
  1375.   computational problems for secure cryptographic properties. For 
  1376.   example, a system called a `Knapsack cipher' was in vogue in the
  1377.   literature for years until it was demonstrated that the instances
  1378.   typically generated could be efficiently broken, and the whole
  1379.   area of research fell out of favor.
  1380.  
  1381. 6.7. What's the difference between the RSA and Diffie-Hellman schemes?
  1382.  
  1383.   stem that requires the dynamic 
  1384.   exchange of keys for every sender-receiver pair (and in practice, 
  1385.   usually every communications session, hence the term `session key').  
  1386.   This two-way key negotiation is useful in further complicating 
  1387.   attacks, but requires additional communications overhead. The RSA 
  1388.   system reduces communications overhead with the ability to have 
  1389.   static, unchanging keys for each receiver that are `advertised' by 
  1390.   a formal `trusted authority' (the hierarchical model) or distributed 
  1391.   in an informal `web of trust'.
  1392.  
  1393. 6.8. What is `authentication' and the `key-exchange problem'?
  1394.  
  1395.   The ``key exchange problem'' involves (1) ensuring that keys are
  1396.   exchanged so that the sender and receiver can perform encryption and
  1397.   decryption, and (2) doing so in such a way that ensures an
  1398.   eavesdropper or outside party cannot break the code. `Authentication'
  1399.   adds the requirement that (3) there is some assurance to the receiver
  1400.   that a message was encrypted by `a given entity' and not `someone 
  1401.   else'.
  1402.  
  1403.   The simplest but least available method to ensure all constraints 
  1404.   above are satisfied (successful key exchange and valid authentication)
  1405.   is employed by private key cryptography: exchanging the key secretly.
  1406.   Note that under this scheme, the problem of authentication is 
  1407.   implicitly resolved. The assumption under the scheme is that only the
  1408.   sender will have the key capable of encrypting sensible messages
  1409.   delivered to the receiver. 
  1410.  
  1411.   While public-key cryptographic methods solve a critical aspect of the 
  1412.   `key-exchange problem', specifically their resistance to analysis
  1413.   even with the presence a passive eavesdropper during exchange of keys, 
  1414.   they do not solve all problems associated with key exchange. In
  1415.   particular, since the keys are considered `public knowledge,'
  1416.   (particularly with RSA) some other mechanism must be
  1417.   developed to testify to authenticity, because possession of keys 
  1418.   alone (sufficient to encrypt intelligible messages) is no evidence
  1419.   of a particular unique identity of the sender.
  1420.  
  1421.   One solution is to develop a key distribution mechanism that assures
  1422.   that listed keys are actually those of the given entities, sometimes
  1423.   called a `trusted authority'. The authority typically does not actually
  1424.   generate keys, but does ensure via some mechanism that the lists of 
  1425.   keys and associated identities kept and advertised for reference
  1426.   by senders and receivers are `correct'. Another method relies on users
  1427.   to distribute and track each other's keys and trust in an informal,
  1428.   distributed fashion. This has been popularized as a viable alternative
  1429.   by the PGP software which calls the model the `web of trust'.
  1430.  
  1431.   Under RSA, if a person wishes to send evidence of their identity in
  1432.   addition to an encrypted message, they simply encrypt some information
  1433.   with their private key called the `signature', additionally included in
  1434.   the message sent under the public-key encryption to the receiver. 
  1435.   The receiver can use the RSA algorithm `in reverse' to verify that the
  1436.   information decrypts sensibly, such that only the given entity could
  1437.   have encrypted the plaintext by use of the secret key. Typically the
  1438.   encrypted `signature' is a `message digest' that comprises a unique
  1439.   mathematical `summary' of the secret message (if the signature were
  1440.   static across multiple messages, once known previous receivers could 
  1441.   use it falsely). In this way, theoretically only the sender of the
  1442.   message could generate their valid signature for that message, thereby
  1443.   authenticating it for the receiver. `Digital signatures' have many 
  1444.   other design properties as described in Section 7.
  1445.  
  1446.  
  1447. 6.9. How fast can people factor numbers?
  1448.  
  1449.   It depends on the size of the numbers, and their form. Numbers
  1450.   in special forms, such as a^n - b for `small' b, are more readily
  1451.   factored through specialized techniques and not necessarily related
  1452.   to the difficulty of factoring in general. Hence a specific factoring 
  1453.   `breakthrough' for a special number form may have no practical value 
  1454.   or relevance to particular instances (and those generated for use
  1455.   in cryptographic systems are specifically `filtered' to resist such
  1456.   approaches.) The most important observation about factoring is that
  1457.   all known algorithms require an exponential amount of time in the
  1458.   _size_ of the number (measured in bits, log2(n) where `n' is the 
  1459.   number). Cryptgraphic algorithms built on the difficulty of factoring
  1460.   generally depend on this exponential-time property. (The distinction
  1461.   of `exponential' vs. `polynomial time' algorithms, or NP vs. P, is a 
  1462.   major area of active computational research, with insights very 
  1463.   closely intertwined with cryptographic security.)
  1464.   
  1465.   In October 1992 Arjen Lenstra and Dan Bernstein factored 2^523 - 1 
  1466.   into primes, using about three weeks of MasPar time. (The MasPar is 
  1467.   a 16384-processor SIMD machine; each processor can add about 200000 
  1468.   integers per second.) The algorithm there is called the ``number field 
  1469.   sieve''; it is quite a bit faster for special numbers like 2^523 - 1 
  1470.   than for general numbers n, but it takes time only 
  1471.   exp(O(log^{1/3} n log^{2/3} log n)) in any case.
  1472.  
  1473.   An older and more popular method for smaller numbers is the ``multiple
  1474.   polynomial quadratic sieve'', which takes time exp(O(log^{1/2} n
  1475.   log^{1/2} log n))---faster than the number field sieve for small n,
  1476.   but slower for large n. The breakeven point is somewhere between 100
  1477.   and 150 digits, depending on the implementations.
  1478.  
  1479.   Factorization is a fast-moving field---the state of the art just a few
  1480.   years ago was nowhere near as good as it is now. If no new methods are
  1481.   developed, then 2048-bit RSA keys will always be safe from
  1482.   factorization, but one can't predict the future. (Before the number
  1483.   field sieve was found, many people conjectured that the quadratic
  1484.   sieve was asymptotically as fast as any factoring method could be.)
  1485.  
  1486. 6.10. What about other public-key cryptosystems?
  1487.  
  1488.   We've talked about RSA because it's well known and easy to describe.
  1489.   But there are lots of other public-key systems around, many of which
  1490.   are faster than RSA or depend on problems more widely believed to be
  1491.   difficult. This has been just a brief introduction; if you really want
  1492.   to learn about the many facets of public-key cryptography, consult the
  1493.   books and journal articles listed in part 10.
  1494.  
  1495. 6.11. What is the ``RSA Factoring Challenge''?
  1496.  
  1497.   In ~1992 the RSA Data Securities Inc., owner and licensor of multiple
  1498.   patents on the RSA hardware and public key cryptographic techniques in
  1499.   general, and maker of various software encryption packages and 
  1500.   libraries, announced on sci.math and elsewhere the creation of an 
  1501.   ongoing Factoring Challenge contest to gauge the state of the art in
  1502.   factoring technology. Every month a series of numbers are posted and
  1503.   monetary awards are given to the first respondent to break them into
  1504.   factors. Very significant hardware resources are required to succeed 
  1505.   by beating other participants. Information can be obtained via 
  1506.   automated reply from
  1507.  
  1508.     challenge-rsa-honor-roll@rsa.com
  1509.     challenge-partition-honor-roll@rsa.com
  1510.  
  1511.  
  1512.  
  1513. Subject: Cryptography FAQ (07/10: Digital Signatures)
  1514.  
  1515. Archive-name: cryptography-faq/part07
  1516. Last-modified: 93/05/04
  1517.  
  1518. This is the seventh of ten parts of the sci.crypt FAQ. The parts are
  1519. mostly independent, but you should read the first part before the rest.
  1520. We don't have the time to send out missing parts by mail, so don't ask.
  1521. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  1522.  
  1523. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  1524. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  1525. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  1526. sci.answers, and news.answers every 21 days.
  1527.  
  1528.  
  1529.  
  1530. Contents:
  1531.  
  1532. 7.1. What is a one-way hash function?
  1533. 7.2. What is the difference between public, private, secret, shared, etc.?
  1534. 7.3. What are MD4 and MD5?
  1535. 7.4. What is Snefru?
  1536.  
  1537.  
  1538. 7.1. What is a one-way hash function?
  1539.  
  1540.   A typical one-way hash function takes a variable-length message and
  1541.   produces a fixed-length hash. Given the hash it is computationally
  1542.   impossible to find a message with that hash; in fact one can't
  1543.   determine any usable information about a message with that hash, not
  1544.   even a single bit. For some one-way hash functions it's also
  1545.   computationally impossible to determine two messages which produce the
  1546.   same hash.
  1547.  
  1548.   A one-way hash function can be private or public, just like an
  1549.   encryption function. Here's one application of a public one-way hash
  1550.   function, like MD5 or Snefru. Most public-key signature systems are
  1551.   relatively slow. To sign a long message may take longer than the user
  1552.   is willing to wait. Solution: Compute the one-way hash of the message,
  1553.   and sign the hash, which is short. Now anyone who wants to verify the
  1554.   signature can do the same thing.
  1555.  
  1556.   Another name for one-way hash function is message digest function.
  1557.  
  1558. 7.2. What is the difference between public, private, secret, shared, etc.?
  1559.  
  1560.   There is a horrendous mishmash of terminology in the literature for a
  1561.   very small set of concepts. Here are the concepts: (1) When an
  1562.   algorithm depends on a key which isn't published, we call it a private
  1563.   algorithm; otherwise we call it a public algorithm. (2) We have
  1564.   encryption functions E and decryption functions D, so that D(E(M)) = M
  1565.   for any message M. (3) We also have hashing functions H and
  1566.   verification functions V, such that V(M,X) = 1 if and only if X = H(M).
  1567.  
  1568.   A public-key cryptosystem has public encryption and private
  1569.   decryption. Checksums, such as the application mentioned in the
  1570.   previous question, have public hashing and public verification.
  1571.   Digital signature functions have private hashing and public
  1572.   verification: only one person can produce the hash for a message,
  1573.   but everyone can verify that the hash is correct.
  1574.  
  1575.   Obviously, when an algorithm depends on a private key, it's meant to
  1576.   be unusable by anyone who doesn't have the key. There's no real
  1577.   difference between a ``shared'' key and a private key: a shared key
  1578.   isn't published, so it's private. If you encrypt data for a friend
  1579.   rather than ``for your eyes only'', are you suddenly doing
  1580.   ``shared-key encryption'' rather than private-key encryption? No.
  1581.  
  1582. 7.3. What are MD4 and MD5?
  1583.  
  1584.   MD4 and MD5 are message digest functions developed by Ron Rivest.
  1585.   Definitions appear in RFC 1320 and RFC 1321 (see part 10). Code is
  1586.   available from [FTPMD].
  1587.  
  1588.   Note that a transcription error was found in the original MD5 draft
  1589.   RFC. The corrected algorithm should be called MD5a, though some
  1590.   people refer to it as MD5.
  1591.  
  1592. 7.4. What is Snefru?
  1593.  
  1594.   Snefru is a family of message digest functions developed by Ralph
  1595.   Merkle. Snefru-8 is an 8-round function, the newest in the family.
  1596.   Definitions appear in Merkle's paper [ME91a]. Code is available from
  1597.   [FTPSF].
  1598.  
  1599.  
  1600. Subject: Cryptography FAQ (08/10: Technical Miscellany)
  1601.  
  1602. Archive-name: cryptography-faq/part08
  1603. Last-modified: 93/08/14
  1604.  
  1605.  
  1606. This is the eighth of ten parts of the sci.crypt FAQ. The parts are
  1607. mostly independent, but you should read the first part before the rest.
  1608. We don't have the time to send out missing parts by mail, so don't ask.
  1609. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  1610.  
  1611. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  1612. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  1613. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  1614. sci.answers, and news.answers every 21 days.
  1615.  
  1616.  
  1617.  
  1618. Contents
  1619.  
  1620. 8.1. How do I recover from lost passwords in WordPerfect?
  1621. 8.2. How do I break a Vigenere (repeated-key) cipher?
  1622. 8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
  1623. 8.4. Is the UNIX crypt command secure?
  1624. 8.5. How do I use compression with encryption?
  1625. 8.6. Is there an unbreakable cipher?
  1626. 8.7. What does ``random'' mean in cryptography?
  1627. 8.8. What is the unicity point (a.k.a. unicity distance)?
  1628. 8.9. What is key management and why is it important?
  1629. 8.10. Can I use pseudo-random or chaotic numbers as a key stream?
  1630. 8.11. What is the correct frequency list for English letters?
  1631. 8.12. What is the Enigma?
  1632. 8.13. How do I shuffle cards?
  1633. 8.14. Can I foil S/W pirates by encrypting my CD-ROM?
  1634. 8.15. Can you do automatic cryptanalysis of simple ciphers?
  1635. 8.16. What is the coding system used by VCR+?
  1636.  
  1637.  
  1638. 8.1. How do I recover from lost passwords in WordPerfect?
  1639.  
  1640.   WordPerfect encryption has been shown to be very easy to break.
  1641.   The method uses XOR with two repeating key streams: a typed password
  1642.   and a byte-wide counter initialized to 1+<the password length>. Full
  1643.   descriptions are given in Bennett [BEN87] and Bergen and Caelli
  1644.   [BER91].
  1645.  
  1646.   Chris Galas writes: ``Someone awhile back was looking for a way to
  1647.   decrypt WordPerfect document files and I think I have a solution. 
  1648.   There is a software company named: Accessdata (87 East 600 South,
  1649.   Orem, UT 84058), 1-800-658-5199 that has a software package that will
  1650.   decrypt any WordPerfect, Lotus 1-2-3, Quatro-Pro, MS Excel and Paradox
  1651.   files. The cost of the package is $185. Steep prices, but if you
  1652.   think your pw key is less than 10 characters, (or 10 char) give them a
  1653.   call and ask for the free demo disk. The demo disk will decrypt files
  1654.   that have a 10 char or less pw key.'' Bruce Schneier says the phone
  1655.   number for AccessData is 801-224-6970.
  1656.  
  1657. 8.2. How do I break a Vigenere (repeated-key) cipher?
  1658.  
  1659.   A repeated-key cipher, where the ciphertext is something like the
  1660.   plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher.
  1661.   If the key is not too long and the plaintext is in English, do the
  1662.   following: 
  1663.  
  1664.   1. Discover the length of the key by counting coincidences.
  1665.   (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of
  1666.   the ciphertext against itself, count those bytes which are equal. 
  1667.   If the two ciphertext portions have used the same key, something
  1668.   over 6% of the bytes will be equal. If they have used different
  1669.   keys, then less than 0.4% will be equal (assuming random 8-bit bytes
  1670.   of key covering normal ASCII text). The smallest displacement which
  1671.   indicates an equal key is the length of the repeated key.
  1672.  
  1673.   2. Shift the text by that length and XOR it with itself. This
  1674.   removes the key and leaves you with text XORed with itself. Since
  1675.   English has about 1 bit of real information per byte, 2 streams of
  1676.   text XORed together has 2 bits of info per 8-bit byte, providing
  1677.   plenty of redundancy for choosing a unique decryption. (And in fact
  1678.   one stream of text XORed with itself has just 1 bit per byte.)
  1679.  
  1680.   If the key is short, it might be even easier to treat this as a
  1681.   standard polyalphabetic substitution. All the old cryptanalysis
  1682.   texts show how to break those. It's possible with those methods, in
  1683.   the hands of an expert, if there's only ten times as much text as key.
  1684.   See, for example, Gaines [GAI44], Sinkov [SIN66].
  1685.  
  1686. 8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
  1687.  
  1688.   Here's one popular method, using the des command:
  1689.  
  1690.     cat file | compress | des private_key | uuencode | mail
  1691.  
  1692.   Meanwhile, there is a de jure Internet standard in the works called
  1693.   PEM (Privacy Enhanced Mail). It is described in RFCs 1421 through
  1694.   1424. To join the PEM mailing list, contact pem-dev-request@tis.com.
  1695.   There is a beta version of PEM being tested at the time of this
  1696.   writing.
  1697.  
  1698.   There are also two programs available in the public domain for encrypting
  1699.   mail: PGP and RIPEM. Both are available by FTP. Each has its own
  1700.   newsgroup: alt.security.pgp and alt.security.ripem. Each has its own FAQ
  1701.   as well.
  1702.  
  1703.   PGP is most commonly used outside the USA since it uses the RSA algorithm
  1704.   without a license and RSA's patent is valid only (or at least primarily)
  1705.   in the USA.
  1706.  
  1707.   RIPEM is most commonly used inside the USA since it uses the RSAREF which
  1708.   is freely available within the USA but not available for shipment outside
  1709.   the USA.
  1710.  
  1711.   Since both programs use a secret key algorithm for encrypting the body of
  1712.   the message (PGP used IDEA; RIPEM uses DES) and RSA for encrypting the
  1713.   message key, they should be able to interoperate freely. Although there
  1714.   have been repeated calls for each to understand the other's formats and
  1715.   algorithm choices, no interoperation is available at this time (as far as
  1716.   we know).
  1717.  
  1718. 8.4. Is the UNIX crypt command secure?
  1719.  
  1720.   No. See [REE84]. There is a program available called cbw (crypt
  1721.   breaker's workbench) which can be used to do ciphertext-only attacks
  1722.   on files encrypted with crypt. One source for CBW is [FTPCB].
  1723.  
  1724. 8.5. How do I use compression with encryption?
  1725.  
  1726.   A number of people have proposed doing perfect compression followed by
  1727.   some simple encryption method (e.g., XOR with a repeated key).  This
  1728.   would work, if you could do perfect compression.  Unfortunately, you can
  1729.   only compress perfectly if you know the exact distribution of possible
  1730.   inputs, and that is almost certainly not possible.
  1731.  
  1732.   Compression aids encryption by reducing the entropy of the plaintext.
  1733.   This increases the amount of ciphertext you can send encrypted under a
  1734.   given number of key bits.  (See "unicity distance")
  1735.  
  1736.   Nearly all practical compression schemes, unless they have been designed
  1737.   with cryptography in mind, produce output that actually starts off with
  1738.   high redundancy. For example, the output of UNIX compress begins with a
  1739.   well-known three-byte ``magic number''.  This produces a field of "known
  1740.   plaintext" which can be used for some forms of cryptanalytic attack.
  1741.   Compression is generally of value, however, because it removes other
  1742.   known plaintext in the middle of the file being encrypted.  In general,
  1743.   the lower the redundancy of the plaintext being fed an encryption
  1744.   algorithm, the more difficult the cryptanalysis of that algorithm.
  1745.  
  1746.   In addition, compression shortens the input file, shortening the output
  1747.   file and reducing the amount of CPU required to do the encryption
  1748.   algorithm, so even if there were no enhancement of security, compression
  1749.   before encryption would be worthwhile.
  1750.  
  1751.   Compression after encryption is silly.  If an encryption algorithm is
  1752.   good, it will produce output which is statistically indistinguishable
  1753. pression algorithm will successfully
  1754.   compress random numbers.  On the other hand, if a compression algorithm
  1755.   succeeds in finding a pattern to compress out of an encryption's output,
  1756.   then a flaw in that algorithm has been found.
  1757.  
  1758. 8.6. Is there an unbreakable cipher?
  1759.  
  1760.   Yes. The one-time pad is unbreakable; see part 4. Unfortunately the
  1761.   one-time pad requires secure distribution of as much key material as
  1762.   plaintext.
  1763.  
  1764.   Of course, a cryptosystem need not be utterly unbreakable to be
  1765.   useful. Rather, it needs to be strong enough to resist attacks by
  1766.   likely enemies for whatever length of time the data it protects is
  1767.   expected to remain valid.
  1768.  
  1769. 8.7. What does ``random'' mean in cryptography?
  1770.  
  1771.   Cryptographic applications demand much more out of a pseudorandom
  1772.   number generator than most applications. For a source of bits to be
  1773.   cryptographically random, it must be computationally impossible to
  1774.   predict what the Nth random bit will be given complete knowledge of
  1775.   the algorithm or hardware generating the stream and the sequence of
  1776.   0th through N-1st bits, for all N up to the lifetime of the source.
  1777.  
  1778.   A software generator (also known as pseudo-random) has the function
  1779.   of expanding a truly random seed to a longer string of apparently
  1780.   random bits. This seed must be large enough not to be guessed by
  1781.   the opponent. Ideally, it should also be truly random (perhaps
  1782.   generated by a hardware random number source).
  1783.  
  1784.   Those who have Sparcstation 1 workstations could, for example,
  1785.   generate random numbers using the audio input device as a source of
  1786.   entropy, by not connecting anything to it. For example,
  1787.  
  1788.         cat /dev/audio | compress - >foo
  1789.  
  1790.   gives a file of high entropy (not random but with much randomness in
  1791.   it). One can then encrypt that file using part of itself as a key,
  1792.   for example, to convert that seed entropy into a pseudo-random
  1793.   string.
  1794.  
  1795.   When looking for hardware devices to provide this entropy, it is
  1796.   important really to measure the entropy rather than just assume that
  1797.   because it looks complicated to a human, it must be "random". For
  1798.   example, disk operation completion times sound like they might be
  1799.   unpredictable (to many people) but a spinning disk is much like a
  1800.   clock and its output completion times are relatively low in entropy.
  1801.  
  1802. 8.8. What is the unicity point (a.k.a. unicity distance)?
  1803.  
  1804.   See [SHA49]. The unicity distance is an approximation to that amount
  1805.   of ciphertext such that the sum of the real information (entropy) in
  1806.   the corresponding source text and encryption key equals the number
  1807.   of ciphertext bits used. Ciphertexts significantly longer than this
  1808.   can be shown probably to have a unique decipherment. This is used to
  1809.   back up a claim of the validity of a ciphertext-only cryptanalysis. 
  1810.   Ciphertexts significantly shorter than this are likely to have
  1811.   multiple, equally valid decryptions and therefore to gain security
  1812.   from the opponent's difficulty choosing the correct one.
  1813.  
  1814.   Unicity distance, like all statistical or information-theoretic
  1815.   measures, does not make deterministic predictions but rather gives
  1816.   probabilistic results: namely, the minimum amount of ciphertext
  1817.   for which it is likely that there is only a single intelligible
  1818.   plaintext corresponding to the ciphertext, when all possible keys
  1819.   are tried for the decryption. Working cryptologists don't normally
  1820.   deal with unicity distance as such. Instead they directly determine
  1821.   the likelihood of events of interest.
  1822.  
  1823.   Let the unicity distance of a cipher be D characters. If fewer than
  1824.   D ciphertext characters have been intercepted, then there is not
  1825.   enough information to distinguish the real key from a set of
  1826.   possible keys. DES has a unicity distance of 17.5 characters,
  1827.   which is less than 3 ciphertext blocks (each block corresponds to
  1828.   8 ASCII characters). This may seem alarmingly low at first, but
  1829.   the unicity distance gives no indication of the computational work
  1830.   required to find the key after approximately D characters have been
  1831.   intercepted.
  1832.  
  1833.   In fact, actual cryptanalysis seldom proceeds along the lines used
  1834.   in discussing unicity distance. (Like other measures such as key
  1835.   size, unicity distance is something that guarantees insecurity if
  1836.   it's too small, but doesn't guarantee security if it's high.) Few
  1837.   practical cryptosystems are absolutely impervious to analysis; all
  1838.   manner of characteristics might serve as entering ``wedges'' to crack
  1839.   some cipher messages. However, similar information-theoretic
  1840.   considerations are occasionally useful, for example, to determine a
  1841.   recommended key change interval for a particular cryptosystem.
  1842.   Cryptanalysts also employ a variety of statistical and
  1843.   information-theoretic tests to help guide the analysis in the most
  1844.   promising directions.
  1845.  
  1846.   Unfortunately, most literature on the application of information
  1847.   statistics to cryptanalysis remains classified, even the seminal
  1848.   1940 work of Alan Turing (see [KOZ84]). For some insight into the
  1849.   possibilities, see [KUL68] and [GOO83].
  1850.  
  1851. 8.9. What is key management and why is it important?
  1852.  
  1853.   One of the fundamental axioms of cryptography is that the enemy is in
  1854.   full possession of the details of the general cryptographic system,
  1855.   and lacks only the specific key data employed in the encryption. (Of
  1856.   course, one would assume that the CIA does not make a habit of telling
  1857.   Mossad about its cryptosystems, but Mossad probably finds out anyway.)
  1858.   Repeated use of a finite amount of key provides redundancy that can
  1859.   eventually facilitate cryptanalytic progress. Thus, especially in
  1860.   modern communication systems where vast amounts of information are
  1861.   transferred, both parties must have not only a sound cryptosystem but
  1862.   also enough key material to cover the traffic.
  1863.  
  1864.   Key management refers to the distribution, authentication, and
  1865.   handling of keys.
  1866.  
  1867.   A publicly accessible example of modern key management technology
  1868.   is the STU III secure telephone unit, which for classified use
  1869.   employs individual coded ``Crypto Ignition Keys'' and a central Key
  1870.   Management Center operated by NSA. There is a hierarchy in that
  1871.   certain CIKs are used by authorized cryptographic control
  1872.   personnel to validate the issuance of individual traffic keys and
  1873.   to perform installation/maintenance functions, such as the
  1874.   reporting of lost CIKs.
  1875.  
  1876.   This should give an inkling of the extent of the key management
  1877.   problem. For public-key systems, there are several related issues,
  1878.   many having to do with ``whom do you trust?''
  1879.  
  1880. 8.10. Can I use pseudo-random or chaotic numbers as a key stream?
  1881.  
  1882.   Chaotic equations and fractals produce an apparent randomness from
  1883.   relatively compact generators. Perhaps the simplest example is a
  1884.   linear congruential sequence, one of the most popular types of random
  1885.   number generators, where there is no obvious dependence between seeds
  1886.   and outputs. Unfortunately the graph of any such sequence will, in a
  1887.   high enough dimension, show up as a regular lattice. Mathematically
  1888.   this lattice corresponds to structure which is notoriously easy for
  1889.   cryptanalysts to exploit. More complicated generators have more
  1890.   complicated structure, which is why they make interesting pictures---
  1891.   but a cryptographically strong sequence will have no computable
  1892.   structure at all.
  1893.  
  1894.   See [KNU81], exercise 3.5-7; [REE77]; and [BOY89].
  1895.  
  1896. 8.11. What is the correct frequency list for English letters?
  1897.  
  1898.   There are three answers to this question, each slightly deeper than
  1899.   the one before. You can find the first answer in various books:
  1900.   namely, a frequency list computed directly from a certain sample of
  1901.   English text.
  1902.  
  1903.   The second answer is that ``the English language'' varies from author
  1904.   to author and has changed over time, so there is no definitive list.
  1905.   Of course the lists in the books are ``correctly'' computed, but
  1906.   they're all different: exactly which list you get depends on which
  1907.   sample was taken. Any particular message will have different
  1908.   statistics from those of the language as a whole.
  1909.  
  1910.   The third answer is that yes, no particular message is going to have
  1911.  general, but for all
  1912.   reasonable statistical uses these slight discrepancies won't matter.
  1913.   In fact there's an entire field called ``Bayesian statistics'' (other
  1914.   buzzwords are ``maximum entropy methods'' and ``maximum likelihood
  1915.   estimation'') which studies questions like ``What's the chance that a
  1916.   text with these letter frequencies is in English?'' and comes up with
  1917.   reasonably robust answers.
  1918.  
  1919.   So make your own list from your own samples of English text. It will
  1920.   be good enough for practical work, if you use it properly.
  1921.  
  1922. 8.12. What is the Enigma?
  1923.  
  1924.   ``For a project in data security we are looking for sources of
  1925.   information about the German Enigma code and how it was broken by
  1926.   the British during WWII.''
  1927.  
  1928.   See [WEL82], [DEA85], [KOZ84], [HOD83], [KAH91].
  1929.  
  1930. 8.13. How do I shuffle cards?
  1931.  
  1932.   Card shuffling is a special case of the permutation of an array of
  1933.   values, using a random or pseudo-random function. All possible output
  1934.   permutations of this process should be equally likely. To do this, you
  1935.   need a random function (modran(x)) which will produce a uniformly
  1936.   distributed random integer in the interval [0..x-1]. Given that
  1937.   function, you can shuffle with the following [C] code: (assuming ARRLTH
  1938.   is the length of array arr[] and swap() interchanges values at the two
  1939.   addresses given)
  1940.  
  1941.   for ( n = ARRLTH-1; n > 0 ; n-- ) swap( &arr[modran( n+1 )], &arr[n] ) ;
  1942.  
  1943.   modran(x) can not be achieved exactly with a simple (ranno() % x) since
  1944.   ranno()'s interval may not be divisible by x, although in most cases the
  1945.   error will be very small. To cover this case, one can take ranno()'s
  1946.   modulus mod x, call that number y, and if ranno() returns a value less
  1947.   than y, go back and get another ranno() value.
  1948.  
  1949.   See [KNU81] for further discussion.
  1950.  
  1951. 8.14. Can I foil S/W pirates by encrypting my CD-ROM?
  1952.  
  1953.   Someone will frequently express the desire to publish a CD-ROM with
  1954.   possibly multiple pieces of software, perhaps with each encrypted
  1955.   separately, and will want to use different keys for each user (perhaps
  1956.   even good for only a limited period of time) in order to avoid piracy.
  1957.  
  1958.   As far as we know, this is impossible, since there is nothing in standard
  1959.   PC or workstation hardware which uniquely identifies the user at the
  1960.   keyboard. If there were such an identification, then the CD-ROM could be
  1961.   encrypted with a key based in part on the one sold to the user and in
  1962.   part on the unique identifier. However, in this case the CD-ROM is one
  1963.   of a kind and that defeats the intended purpose.
  1964.  
  1965.   If the CD-ROM is to be encrypted once and then mass produced, there must
  1966.   be a key (or set of keys) for that encryption produced at some stage in
  1967.   the process. That key is useable with any copy of the CD-ROM's data.
  1968.   The pirate needs only to isolate that key and sell it along with the
  1969.   illegal copy.
  1970.  
  1971. 8.15. Can you do automatic cryptanalysis of simple ciphers?
  1972.  
  1973.   Certainly. For commercial products you can try AccessData; see
  1974.   question 8.1. We are not aware of any FTP sites for such software,
  1975.   but there are many papers on the subject. See [PEL79], [LUC88],
  1976.   [CAR86], [CAR87], [KOC87], [KOC88], [KIN92], [KIN93], [SPI93].
  1977.  
  1978. 8.16. What is the coding system used by VCR+?
  1979.  
  1980.   One very frequently asked question in sci.crypt is how the VCR+ codes
  1981.   work. The codes are used to program a VCR based on numerical input.
  1982.   See [SHI92] for an attempt to describe it.
  1983.  
  1984.  
  1985.  
  1986. Newsgroups: sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
  1987.  
  1988. Archive-name: cryptography-faq/part09
  1989. Last-modified: 93/08/14
  1990.  
  1991.  
  1992. This is the ninth of ten parts of the sci.crypt FAQ. The parts are
  1993. mostly independent, but you should read the first part before the rest.
  1994. We don't have the time to send out missing parts by mail, so don't ask.
  1995. Notes such as ``[KAH67]'' refer to the reference list in the last part.
  1996.  
  1997. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  1998. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  1999. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  2000. sci.answers, and news.answers every 21 days.
  2001.  
  2002.  
  2003. Contents:
  2004.  
  2005. 9.1. What is the National Security Agency (NSA)?
  2006. 9.2. What are the US export regulations?
  2007. 9.3. What is TEMPEST?
  2008. 9.4. What are the Beale Ciphers, and are they a hoax?
  2009. 9.5. What is the American Cryptogram Association, and how do I get in touch?
  2010. 9.6. Is RSA patented?
  2011. 9.7. What about the Voynich manuscript?
  2012.  
  2013.  
  2014. 9.1. What is the National Security Agency (NSA)?
  2015.  
  2016.   The NSA is the official communications security body of the U.S.
  2017.   government. It was given its charter by President Truman in the early
  2018.   50's, and has continued research in cryptology till the present. The 
  2019.   NSA is known to be the largest employer of mathematicians in the world,
  2020.   and is also the largest purchaser of computer hardware in the
  2021.   world. Governments in general have always been prime employers of
  2022.   cryptologists. The NSA probably possesses cryptographic expertise many
  2023.   years ahead of the public state of the art, and can undoubtedly break
  2024.   many of the systems used in practice; but for reasons of national
  2025.   security almost all information about the NSA is classified.
  2026.  
  2027.   Bamford's book [BAMFD] gives a history of the people and operations of
  2028.   the NSA. The following quote from Massey [MAS88] highlights the
  2029.   difference between public and private research in cryptography:
  2030.  
  2031.   ``... if one regards cryptology as the prerogative of government,
  2032.   one accepts that most cryptologic research will be conducted
  2033.   behind closed doors. Without doubt, the number of workers engaged
  2034.   today in such secret research in cryptology far exceeds that of
  2035.   those engaged in open research in cryptology. For only about 10
  2036.   years has there in fact been widespread open research in
  2037.   cryptology. There have been, and will continue to be, conflicts
  2038.   between these two research communities. Open research is common
  2039.   quest for knowledge that depends for its vitality on the open
  2040.   exchange of ideas via conference presentations and publications in
  2041.   scholarly journals. But can a government agency, charged with
  2042.   responsibilities of breaking the ciphers of other nations,
  2043.   countenance the publication of a cipher that it cannot break? Can
  2044.   a researcher in good conscience publish such a cipher that might
  2045.   undermine the effectiveness of his own government's code-breakers?
  2046.   One might argue that publication of a provably-secure cipher would
  2047.   force all governments to behave like Stimson's `gentlemen', but one
  2048.   must be aware that open research in cryptography is fraught with
  2049.   political and ethical considerations of a severity than in most
  2050.   scientific fields. The wonder is not that some conflicts have
  2051.   occurred between government agencies and open researchers in
  2052.   cryptology, but rather that these conflicts (at least those of which
  2053.   we are aware) have been so few and so mild.''
  2054.  
  2055. 9.2. What are the US export regulations?
  2056.  
  2057.   In a nutshell, there are two government agencies which control
  2058.   export of encryption software. One is the Bureau of Export
  2059.   Administration (BXA) in the Department of Commerce, authorized by
  2060.   the Export Administration Regulations (EAR). Another is the Office
  2061.   of Defense Trade Controls (DTC) in the State Department, authorized
  2062.   by the International Traffic in Arms Regulations (ITAR). As a rule
  2063.   of thumb, BXA (which works with COCOM) has less stringent
  2064.   requirements, but DTC (which takes orders from NSA) wants to see
  2065.   everything first and can refuse to transfer jurisdiction to BXA.
  2066.  
  2067.   The newsgroup misc.legal.computing carries many interesting
  2068.   discussions on the laws surrounding cryptographic export, what
  2069.   people think about those laws, and many other complex issues which
  2070.   go beyond the scope of technical groups like sci.crypt. Make sure to
  2071.   consult your lawyer before doing anything which will get you thrown in
  2072.   jail; if you are lucky, your lawyer might know a lawyer who has at
  2073.   least heard of the ITAR.
  2074.  
  2075. 9.3. What is TEMPEST?
  2076.  
  2077.   TEMPEST is a standard for electromagnetic shielding for computer
  2078.   equipment. It was created in response to the discovery that
  2079.   information can be read from computer radiation (e.g., from a CRT) at
  2080.   quite a distance and with little effort.
  2081.  
  2082.   Needless to say, encryption doesn't do much good if the cleartext
  2083.   is available this way.
  2084.  
  2085. 9.4. What are the Beale Ciphers, and are they a hoax?
  2086.  
  2087.   (Thanks to Jim Gillogly for this information and John King for
  2088.   corrections.)
  2089.  
  2090.   The story in a pamphlet by J. B. Ward (1885) goes: Thomas
  2091.   Jefferson Beale and a party of adventurers accumulated a huge mass
  2092.   of treasure and buried it in Bedford County, Virginia, leaving
  2093.   three ciphers with an innkeeper; the ciphers describe the
  2094.   location, contents, and intended beneficiaries of the treasure.
  2095.   Ward gives a decryption of the second cipher (contents) called B2;
  2096.   it was encrypted as a book cipher using the initial letters of the
  2097.   Declaration of Independence (DOI) as key. B1 and B3 are unsolved;
  2098.   many documents have been tried as the key to B1.
  2099.  
  2100.   Aficionados can join a group that attempts to solve B1 by various
  2101.   means with an eye toward splitting the treasure:
  2102.  
  2103.   The Beale Cypher Association
  2104.   P.O. Box 975
  2105.   Beaver Falls, PA 15010
  2106.  
  2107.   You can get the ciphers from the rec.puzzles FAQL by including the
  2108.   line:
  2109.  
  2110.   send index
  2111.  
  2112.   in a message to netlib@peregrine.com and following the directions.
  2113.   (There are apparently several different versions of the cipher
  2114.   floating around. The correct version is based on the 1885 pamphlet,
  2115.   says John King <kingj@hpcc01.corp.hp.com>.)
  2116.  
  2117.   Some believe the story is a hoax. Kruh [KRU88] gives a long list of
  2118.   problems with the story. Gillogly [GIL80] decrypted B1 with the DOI
  2119.   and found some unexpected strings, including ABFDEFGHIIJKLMMNOHPP.
  2120.   Hammer (president of the Beale Cypher Association) agrees that this
  2121.   string couldn't appear by chance, but feels there must be an
  2122.   explanation; Gwyn (sci.crypt expert) is unimpressed with this
  2123.   string.
  2124.  
  2125. 9.5. What is the American Cryptogram Association, and how do I get in touch?
  2126.  
  2127.   The ACA is an organization devoted to cryptography, with an emphasis
  2128.   on cryptanalysis of systems that can be attacked either with
  2129.   pencil-and-paper or computers. Its organ ``The Cryptogram'' includes
  2130.   articles and challenge ciphers. Among the more than 50 cipher types in
  2131.   English and other languages are simple substitution, Playfair,
  2132.   Vigenere, bifid, Bazeries, grille, homophonic, and cryptarithm.
  2133.  
  2134.   Dues are $15 for one year (6 issues); more outside of North America;
  2135.   less for students under 18 and seniors. Subscriptions should be sent
  2136.   to ACA Treasurer, P.O. Box 198, Vernon Hills, IL 60061-0198.
  2137.  
  2138. 9.6. Is RSA patented?
  2139.  
  2140.   Yes. The patent number is 4,405,829, filed 12/14/77, granted 9/20/83.
  2141. been
  2142.   granted, algorithm patents in general, and related legal and moral
  2143.   issues, see comp.patents and misc.legal.computing. For information
  2144.   about the League for Programming Freedom see [FTPPF]. Note that one of
  2145.   the original purposes of comp.patents was to collect questions such as
  2146.   ``should RSA be patented?'', which often flooded sci.crypt and other
  2147.   technical newsgroups, into a more appropriate forum.
  2148.  
  2149. 9.7. What about the Voynich manuscript?
  2150.  
  2151.   The Voynich manuscript is an elaborately lettered and illustrated
  2152.   document, in a script never deciphered. It has been handed down for
  2153.   centuries by a line of art collectors and has uncertain origination.
  2154.   Much speculation and attention has been focused on its potential
  2155.   meaning.
  2156.  
  2157.   nelson@reed.edu (Nelson Minar) says there is a mailing list on the
  2158.   subject. The address to write to subscribe to the VMS mailing list
  2159.   is: <voynich-request@rand.org>
  2160.  
  2161.   the ftp archive is: rand.org:/pub/voynich
  2162.  
  2163.   There's all sorts of information about the manuscript itself, of
  2164.   course. A good bibliography can be found on the ftp site. [KAH67]
  2165.   gives a good introduction.
  2166.  
  2167.  
  2168.  
  2169. Newsgroups: sci.crypt,talk.politics.crypto,sci.answers,news.answers,talk.answers
  2170.  
  2171. Archive-name: cryptography-faq/part10
  2172. Last-modified: 93/08/14
  2173.  
  2174.  
  2175. This is the tenth of ten parts of the sci.crypt FAQ. The parts are
  2176. mostly independent, but you should read the first part before the rest.
  2177. We don't have the time to send out missing parts by mail, so don't ask.
  2178. Notes such as ``[KAH67]'' refer to the reference list in this part.
  2179.  
  2180. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu 
  2181. as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography 
  2182. FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, 
  2183. sci.answers, and news.answers every 21 days.
  2184.  
  2185.  
  2186.  
  2187. Contents
  2188.  
  2189. 10.1. Books on history and classical methods
  2190. 10.2. Books on modern methods
  2191. 10.3. Survey articles
  2192. 10.4. Reference articles
  2193. 10.5. Journals, conference proceedings
  2194. 10.6. Other
  2195. 10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
  2196. 10.8. Electronic sources
  2197. 10.9. RFCs (available from [FTPRF])
  2198. 10.10. Related newsgroups
  2199.  
  2200.  
  2201. 10.1. Books on history and classical methods
  2202.  
  2203.   [FRIE1] Lambros D. Callimahos, William F. Friedman, Military Cryptanalytics.
  2204.           Aegean Park Press, ?.
  2205.   [DEA85] Cipher A. Deavours & Louis Kruh, Machine Cryptography and
  2206.           Modern Cryptanalysis. Artech House, 610 Washington St.,
  2207.           Dedham, MA 02026, 1985.
  2208.   [FRIE2] William F. Friedman, Solving German Codes in World War I.
  2209.           Aegean Park Press, ?.
  2210.   [GAI44] H. Gaines, Cryptanalysis, a study of ciphers and their
  2211.           solution. Dover Publications, 1944.
  2212.   [HIN00] F.H.Hinsley, et al., British Intelligence in the Second
  2213.           World War. Cambridge University Press. (vol's 1, 2, 3a, 3b
  2214.           & 4, so far). XXX Years and authors, fix XXX
  2215.   [HOD83] Andrew Hodges, Alan Turing: The Enigma. Burnett Books
  2216.           Ltd., 1983
  2217.   [KAH91] David Kahn, Seizing the Enigma. Houghton Mifflin, 1991.
  2218.   [KAH67] D. Kahn, The Codebreakers. Macmillan Publishing, 1967.
  2219.           [history] [The abridged paperback edition left out most
  2220.           technical details; the original hardcover edition is
  2221.           recommended.]
  2222.   [KOZ84] W. Kozaczuk, Enigma. University Publications of America, 1984
  2223.   [KUL76] S. Kullback, Statistical Methods in Cryptanalysis. Aegean
  2224.           Park Press, 1976.
  2225.   [SIN66] A. Sinkov, Elementary Cryptanalysis. Math. Assoc. Am. 1966.
  2226.   [WEL82] Gordon Welchman, The Hut Six Story. McGraw-Hill, 1982.
  2227.   [YARDL] Herbert O. Yardley, The American Black Chamber. Aegean Park
  2228.           Press, ?.
  2229.  
  2230. 10.2. Books on modern methods
  2231.  
  2232.   [BEK82] H. Beker, F. Piper, Cipher Systems. Wiley, 1982.
  2233.   [BRA88] G. Brassard, Modern Cryptology: a tutorial.
  2234.           Spinger-Verlag, 1988.
  2235.   [DEN82] D. Denning, Cryptography and Data Security. Addison-Wesley
  2236.           Publishing Company, 1982.
  2237.   [KOB89] N. Koblitz, A course in number theory and cryptography.
  2238.           Springer-Verlag, 1987.
  2239.   [KON81] A. Konheim, Cryptography: a primer. Wiley, 1981.
  2240.   [MEY82] C. Meyer and S. Matyas, Cryptography: A new dimension in
  2241.           computer security. Wiley, 1982.
  2242.   [PAT87] Wayne Patterson, Mathematical Cryptology for Computer
  2243.           Scientists and Mathematicians. Rowman & Littlefield, 1987.
  2244.   [PFL89] C. Pfleeger, Security in Computing. Prentice-Hall, 1989.
  2245.   [PRI84] W. Price, D. Davies, Security for computer networks. Wiley, 1984. 
  2246.   [RUE86] R. Rueppel, Design and Analysis of Stream Ciphers.
  2247.           Springer-Verlag, 1986.
  2248.   [SAL90] A. Saloma, Public-key cryptography. Springer-Verlag, 1990.
  2249.   [WEL88] D. Welsh, Codes and Cryptography. Claredon Press, 1988.
  2250.  
  2251. 10.3. Survey articles
  2252.  
  2253.   [ANG83] D. Angluin, D. Lichtenstein, Provable Security in Crypto-
  2254.           systems: a survey. Yale University, Department of Computer
  2255.           Science, #288, 1983.
  2256.   [BET90] T. Beth, Algorithm engineering for public key algorithms.
  2257.           IEEE Selected Areas of Communication, 1(4), 458--466,
  2258.           1990.
  2259.   [DAV83] M. Davio, J. Goethals, Elements of cryptology. in Secure
  2260.           Digital Communications, G. Longo ed., 1--57, 1983.
  2261.   [DIF79] W. Diffie, M. Hellman, Privacy and Authentication: An
  2262.           introduction to cryptography. IEEE proceedings, 67(3),
  2263.           397--427, 1979.
  2264.   [DIF88] W. Diffie, The first ten years of public key cryptography.
  2265.           IEEE proceedings, 76(5), 560--577, 1988.
  2266.   [FEI73] H. Feistel, Cryptography and Computer Privacy. Scientific 
  2267.           American, 228(5), 15--23, 1973.
  2268.   [FEI75] H. Feistel, H, W. Notz, J. Lynn Smith. Some cryptographic
  2269.           techniques for machine-to-machine data communications,
  2270.           IEEE IEEE proceedings, 63(11), 1545--1554, 1975.
  2271.   [HEL79] M. Hellman, The mathematics of public key cryptography.
  2272.           Scientific American, 130--139, 1979.
  2273.   [LAK83] S. Lakshmivarahan, Algorithms for public key
  2274.           cryptosystems. In Advances in Computers, M. Yovtis ed.,
  2275.           22, Academic Press, 45--108, 1983.
  2276.   [LEM79] A. Lempel, Cryptology in transition, Computing Surveys,
  2277.           11(4), 285--304, 1979.
  2278.   [MAS88] J. Massey, An introduction to contemporary cryptology, IEEE
  2279.           proceedings, 76(5), 533--549, 1988.
  2280.   [SIM91] G. Simmons (ed.), Contemporary Cryptology: the Science of
  2281.           Information Integrity. IEEE press, 1991.
  2282.  
  2283. 10.4. Reference articles
  2284.  
  2285.   [AND83] D. Andelman, J. Reeds, On the cryptanalysis of rotor and
  2286.           substitution-permutation networks. IEEE Trans. on Inform.
  2287.           Theory, 28(4), 578--584, 1982.
  2288.   [BEN87] John Bennett, Analysis of the Encryption Algorithm Used in
  2289.           the WordPerfect Word Processing Program. Cryptologia 11(4),
  2290.           206--210, 1987.
  2291.   [BER91] H. A. Bergen and W. J. Caelli, File Security in WordPerfect
  2292.           5.0. Cryptologia 15(1), 57--66, January 1991.
  2293.   [BIH91] E. Biham and A. Shamir, Differential cryptanalysis of
  2294.           DES-like cryptosystems. Journal of Cryptology, vol. 4, #1,
  2295.           3--72, 1991.
  2296.   [BI91a] E. Biham, A. Shamir, Differential cryptanalysis of Snefru,
  2297.           Khafre, REDOC-II, LOKI and LUCIFER. In Proceedings of CRYPTO
  2298.           '91, ed. by J. Feigenbaum, 156--171, 1992.
  2299.   [BOY89] J. Boyar, Inferring Sequences Produced by Pseudo-Random
  2300.           Number Generators. Journal of the ACM, 1989.
  2301.   [BRI86] E. Brickell, J. Moore, M. Purtill, Structure in the
  2302.           S-boxes of DES. In Proceedings of CRYPTO '86, A. M. Odlyzko
  2303.           ed., 3--8, 1987.
  2304.   [BRO89] L. Brown, A proposed design for an extended DES, Computer
  2305.           Security in the Computer Age. Elsevier Science Publishers
  2306.           B.V. (North Holland), IFIP, W. J. Caelli ed., 9--22, 1989.
  2307.   [BRO90] L. Brown, J. Pieprzyk, J. Seberry, LOKI - a cryptographic
  2308.           primitive for authentication and secrecy applications.
  2309.           In Proceedings of AUSTCRYPT 90, 229--236, 1990.
  2310.   [CAE90] H. Gustafson, E. Dawson, W. Caelli, Comparison of block
  2311.           ciphers. In Proceedings of AUSCRYPT '90, J. Seberry and J.
  2312.           Piepryzk eds., 208--220, 1990.
  2313.   [CAM93] K. W. Campbell, M. J. Wiener, Proof the DES is Not a Group.
  2314.           In Proceedings of CRYPTO '92, 1993.
  2315.   [CAR86] John Carrol and Steve Martin, The Automated Cryptanalysis
  2316.           of Substitution Ciphers. Cryptologia 10(4), 193--209, 1986.
  2317.   [CAR87] John Carrol and Lynda Robbins, Automated Cryptanalysis of
  2318.           Polyalphabetic Ciphers. Cryptologia 11(4), 193--205, 1987.
  2319.   [ELL88] Carl M. Ellison, A Solution of the Hebern Messages. Cryptologia,
  2320.           vol. XII, #3, 144-158, Jul 1988.
  2321.   [EVE83] S. Even, O. Goldreich, DES-like functions can generate the
  2322.           alternating group. IEEE Trans. on Inform. Theory, vol. 29,
  2323.           #6, 863--865, 1983.
  2324.   [GAR91] G. Garon, R. Outerbridge, DES watch: an examination of the
  2325.           sufficiency of the Data Encryption Standard for financial
  2326.           institutions in the 1990's. Cryptologia, vol. XV, #3,
  2327.           177--193, 1991.
  2328.   [GIL80] Gillogly, ?. Cryptologia 4(2), 1980.
  2329.   [GM82]  Shafi Goldwasser, Silvio Micali, Probabilistic Encryption and
  2330.           How To Play Mental Poker Keeping Secret All Partial Information.
  2331.           Proceedings of the Fourteenth Annual ACM Symposium on Theory of
  2332.           Computing, 1982.
  2333.   [HUM83] D. G. N. Hunter and A. R. McKenzie, Experiments with
  2334.           Relaxation Algorithms for Breaking Simple Substitution
  2335.           Ciphers. Computer Journal 26(1), 1983.
  2336.   [KAM78] J. Kam, G. Davida, A structured design of substitution-
  2337.           permutation encryption networks. IEEE Trans. Information
  2338.           Theory, 28(10), 747--753, 1978.
  2339.   [KIN78] P. Kinnucan, Data encryption gurus: Tuchman and Meyer.
  2340.           Cryptologia, vol. II #4, 371--XXX, 1978.
  2341.   [KIN92] King and Bahler, Probabilistic Relaxation in the
  2342.           Cryptanalysis of Simple Substitution Ciphers. Cryptologia
  2343.           16(3), 215--225, 1992.
  2344.   [KIN93] King and Bahler, An Algorithmic Solution of Sequential
  2345.           Homophonic Ciphers. Cryptologia 17(2), in press.
  2346.   [KOC87] Martin Kochanski, A Survey of Data Insecurity Packages.
  2347.           Cryptologia 11(1), 1--15, 1987.
  2348.   [KOC88] Martin Kochanski, Another Data Insecurity Package.
  2349.           Cryptologia 12(3), 165--177, 1988.
  2350.   [KRU88] Kruh, ?. Cryptologia 12(4), 1988.
  2351.   [LAI90] X. Lai, J. Massey, A proposal for a new block encryption 
  2352.           standard. EUROCRYPT 90, 389--404, 1990.
  2353.   [LUB88] C. Rackoff, M. Luby, How to construct psuedorandom
  2354.           permutations from psuedorandom functions. SIAM Journal of
  2355.           Computing, vol. 17, #2, 373--386, 1988.
  2356.   [LUC88] Michael Lucks, A Constraint Satisfaction Algorithm for the
  2357.           Automated Decryption of Simple Substitution Ciphers. In
  2358.           CRYPTO '88.
  2359.   [MAS88] J. Massey, An introduction to contemporary cryptology.
  2360.           IEEE proceedings, 76(5), 533--549, 1988.
  2361.   [ME91a] R. Merkle, Fast software encryption functions. In Proceedings
  2362.           of CRYPTO '90, Menezes and Vanstone ed., 476--501, 1991.
  2363.   [MEY78] C. Meyer, Ciphertext/plaintext and ciphertext/key
  2364.           dependence vs. number of rounds for the Data Encryption
  2365.           Standard. AFIPS Conference proceedings, 47, 1119--1126,
  2366.           1978.
  2367.   [NBS77] Data Encryption Standard. National Bureau of Standards,
  2368.           FIPS PUB 46, Washington, DC, January 1977.
  2369.   [PEL79] S. Peleg and A. Rosenfeld, Breaking Substitution Ciphers
  2370.           Using a Relaxation Algorithm. CACM 22(11), 598--605, 1979.
  2371.   [REE77] J. Reeds, `Cracking' a Random Number Generator.
  2372.           Cryptologia 1(1), 20--26, 1977.
  2373.   [REE84] J. A. Reeds and P. J. Weinberger, File Security and the UNIX
  2374.           Crypt Command. AT&T Bell Laboratories Technical Journal,
  2375.           Vol. 63 #8, part 2, 1673--1684, October, 1984.
  2376.   [SHA49] C. Shannon, Communication Theory of Secrecy Systems. Bell
  2377.           System Technical Journal 28(4), 656--715, 1949.
  2378.   [SHE88] B. Kaliski, R. Rivest, A. Sherman, Is the Data Encryption
  2379.           Standard a Group. Journal of Cryptology, vol. 1, #1,
  2380.           1--36, 1988.
  2381.   [SHI88] A. Shimizu, S. Miyaguchi, Fast data encipherment algorithm
  2382.           FEAL. EUROCRYPT '87, 267--278, 1988.
  2383.   [SHI92] K. Shirriff, C. Welch, A. Kinsman, Decoding a VCR Controller
  2384.           Code. Cryptologia 16(3), 227--234, 1992.
  2385.   [SOR84] A. Sorkin, LUCIFER: a cryptographic algorithm.
  2386.           Cryptologia, 8(1), 22--35, 1984.
  2387.   [SPI93] R. Spillman et al., Use of Genetic Algorithms in
  2388.           Cryptanalysis of Simple Substitution Ciphers. Cryptologia
  2389.           17(1), 31--44, 1993.
  2390.         
  2391. 10.5. Journals, conference proceedings
  2392.  
  2393.   CRYPTO
  2394.   Eurocrypt
  2395.   IEEE Transactions on Information Theory
  2396.   Cryptologia: a cryptology journal, quarterly since Jan 1977.
  2397.           Cryptologia; Rose-Hulman Institute of Technology; Terre Haute
  2398.           Indiana 47803 [general: systems, analysis, history, ...]
  2399.   Journal of Cryptology; International Association for Cryptologic
  2400.           Research; published by Springer Verlag (quarterly since
  2401.           1988).
  2402.   The Cryptogram (Journal of the American Cryptogram Association);
  2403.           18789 West Hickory Street; Mundelein, IL 60060; [primarily
  2404.           puzzle cryptograms of various sorts]
  2405.   Cryptosystems Journal, Published by Tony Patti, P.O. Box 188,
  2406.           Newtown PA, USA 18940-0188 or tony_s_patti@cup.portal.com.
  2407.           Publisher's comment: Includes complete cryptosystems with
  2408.           source and executable programs on diskettes. Tutorial. The
  2409.           typical cryptosystems supports multi-megabit keys and Galois
  2410.           Field arithmetic. Inexpensive hardware random number
  2411.           generator details.
  2412.   Computer and Communication Security Reviews, published by Ross Anderson.
  2413.           Sample issue available from various ftp sites, including
  2414.           black.ox.ac.uk. Editorial c/o rja14@cl.cam.ac.uk. Publisher's
  2415.           comment: We review all the conference proceedings in this field,
  2416.           including not just Crypto and Eurocrypt, but regional gatherings
  2417.           like Auscrypt and Chinacrypt. We also abstract over 50 journals,
  2418.           and cover computer security as well as cryptology, so readers can
  2419.           see the research trends in applications as well as theory.
  2420.   Infosecurity News, MIS Training Institute Press, Inc. 498 Concord Street
  2421.           Framingham MA 01701-2357. This trade journal is oriented toward 
  2422.           administrators and covers viruses, physical security, hackers, 
  2423.           and so on more than cryptology. Furthermore, most of the articles 
  2424.           are written by vendors and hence are biased.  Nevertheless, there 
  2425.           are occasionally some rather good cryptography articles.
  2426.  
  2427. 10.6. Other
  2428.  
  2429.   Address of note: Aegean Park Press, P.O. Box 2837, Laguna Hills, CA
  2430.   92654-0837. Answering machine at 714-586-8811.  Toll Free at 800 736-
  2431.   3587, and FAX at 714 586-8269.
  2432.  
  2433.   The ``Orange Book'' is DOD 5200.28-STD, published December 1985 as
  2434.   part of the ``rainbow book'' series. Write to Department of Defense,
  2435.   National Security Agency, ATTN: S332, 9800 Savage Road, Fort Meade, MD
  2436.   20755-6000, and ask for the Trusted Computer System Evaluation
  2437.   Criteria. Or call 301-766-8729.
  2438.  
  2439.   The ``Orange Book'' will eventually be replaced by the U.S. Federal 
  2440.   Criteria for Information Technology Security (FC) online at the NIST
  2441.   site [FTPNS], which also contains information on other various proposed 
  2442.   and active federal standards.
  2443.  
  2444.   [BAMFD] Bamford, The Puzzle Palace. Penguin Books, ?.
  2445.   [GOO83] I. J. Good, Good Thinking: the foundations of probability and
  2446.           its applications. University of Minnesota Press, 1983.
  2447.   [KNU81] D. E. Knuth, The Art of Computer Programming, volume 2:
  2448.           Seminumerical Algorithms. Addison-Wesley, 1981.
  2449.   [KUL68] Soloman Kullback, Information Theory and Statistics.
  2450.           Dover, 1968.
  2451.   [YAO88] A. Yao, Computational Information Theory. In Complexity in
  2452.           Information Theory, ed. by Abu-Mostafa, 1988.
  2453.  
  2454. 10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
  2455.  
  2456.   Many textbooks on cryptography contain complete reprints of the FIPS
  2457.   standards, which are not copyrighted.
  2458.  
  2459.   The following standards may be ordered from the
  2460.       U.S. Department of Commerce, National Technical Information Service,
  2461.       Springfield, VA 22161.
  2462.  
  2463.       FIPS PUB 46-1 Data Encryption Standard  (this is DES)
  2464.       FIPS PUB 74   Guidelines for Implementing as Using the NBS DES
  2465.       FIPS PUB 81   DES Modes of Operation
  2466.       FIPS PUB 113  Computer Data Authentication (using DES)
  2467.  
  2468.   The following standards may be ordered from the
  2469.       American National Standards Institute Sales Office,
  2470.       1430 Broadway, New York, NY 10018.
  2471.       Phone 212.642.4900
  2472.  
  2473.       ANSI X3.92-1981  Data Encryption Algorithm (identical to FIPS 46-1)
  2474.       ANSI X3.106-1983 DEA Modes of Operation    (identical to FIPS 113)
  2475.  
  2476.   Notes:  Figure 3 in FIPS PUB 46-1 is in error, but figure 3 in X3.92-1981
  2477.       is correct. The text is correct in both publications.
  2478.  
  2479.  
  2480. 10.8. Electronic sources
  2481.  
  2482.   Anonymous ftp:
  2483.  
  2484.   [FTPAL] kampi.hut.fi:alo/des-dist.tar.Z
  2485.   [FTPBK] ftp.uu.net:bsd-sources/usr.bin/des/
  2486.   [FTPCB] ftp.uu.net:usenet/comp.sources.unix/volume10/cbw/
  2487.   [FTPCP] soda.berkely.edu:/pub/cypherpunks
  2488.   [FTPDF] ftp.funet.fi:pub/unix/security/destoo.tar.Z
  2489.   [FTPDQ] rsa.com:pub/faq/
  2490.   [FTPEY] ftp.psy.uq.oz.au:pub/DES/
  2491.   [FTPMD] rsa.com:?
  2492.   [FTPMR] ripem.msu.edu:pub/crypt/newdes.tar.Z
  2493.   [FTPNS] csrc.nist.gov:/bbs/nistpubs
  2494.   [FTPOB] ftp.3com.com:Orange-book
  2495.   [FTPPF] prep.ai.mit.edu:pub/lpf/
  2496.   [FTPPK] ucsd.edu:hamradio/packet/tcpip/crypto/des.tar.Z
  2497.   [FTPRF] nic.merit.edu:documents/rfc/
  2498.   [FTPSF] beta.xerox.com:pub/hash/
  2499.   [FTPSO] chalmers.se:pub/des/des.1.0.tar.Z
  2500.   [FTPTR] ripem.msu.edu:pub/crypt/other/tran.tar.Z
  2501.   [FTPUF] ftp.uu.net:usenet/comp.sources.unix/volume28/ufc-crypt/
  2502.   [FTPWP] garbo.uwasa.fi:pc/util/wppass2.zip
  2503.  
  2504. 10.9. RFCs (available from [FTPRF])
  2505.  
  2506.   [1424]  B. Kaliski, Privacy Enhancement for Internet Electronic Mail:
  2507.           Part IV: Key Certification and Related Services. RFC 1424,
  2508.           February 1993.
  2509.   [1423]  D. Balenson, Privacy Enhancement for Internet Electronic Mail:
  2510.           Part III: Algorithms, Modes, and Identifiers. RFC 1423,
  2511.           February 1993.
  2512.   [1422]  S. Kent, Privacy Enhancement for Internet Electronic Mail:
  2513.           Part II: Certificate-Based Key Management. RFC 1422, February
  2514.           1993.
  2515.   [1421]  J. Linn, Privacy Enhancement for Internet Electronic Mail:
  2516.           Part I: Message Encryption and Authentication Procedures. RFC
  2517.           1421, February 1993.
  2518.  
  2519. 10.10. Related newsgroups
  2520.  
  2521.   There are other newsgroups which a sci.crypt reader might want also to
  2522.   read. Some have their own FAQs as well.
  2523.  
  2524.   alt.privacy.clipper           Clipper, Capstone, Skipjack, Key Escrow
  2525.   alt.security                  general security discussions
  2526.   alt.security.index            index to alt.security
  2527.   alt.security.pgp              discussion of PGP
  2528.   alt.security.ripem            discussion of RIPEM
  2529.   alt.society.civil-liberty     general civil liberties, including privacy
  2530.   comp.compression              discussion of compression algorithms and code
  2531.   comp.org.eff.news             News reports from EFF
  2532.   comp.org.eff.talk             discussion of EFF related issues
  2533.   comp.patents                  discussion of S/W patents, including RSA
  2534.   comp.risks                    some mention of crypto and wiretapping
  2535.   comp.society.privacy          general privacy issues
  2536.   comp.security.announce        announcements of security holes
  2537.   misc.legal.computing          software patents, copyrights, computer laws
  2538.   sci.math                      general math discussion
  2539.  
  2540.  
  2541.  
  2542.  
  2543.  
  2544.  
  2545.